# _*_ coding utf-8 _*_
# FILENAME：.py
# DESCRIPTION:
# AUTH:
# DATE: 2022/6/82:45 下午

import traceback
import time
import os
import queue
import logging
import datetime
import numpy as np
import pandas as pd
import pydash
import math

from multiprocessing import Process, Queue, cpu_count
from copy import deepcopy
from algorithm.common import CommonUtils
from constant import CacheType
from models.baseModel import get_session
from models.inventoryModel import InventoryModel
from models.orderPlanModel import OrderPlanModel, OrderPlanPartsModel, OrderPlanInventoryModel
from models.requireModel import RequireModel
from models.requireSummaryModel import RequireSummaryModel
from utils.cacheUtils import Cache

# --------------------------------- Modify By fux -------------------------------
from timeit import default_timer as xftimer


def get_input_van_scheme(van_info):
    vans_scheme_list = []

    lower_index = 1
    upper_index = len(van_info)

    vans_scheme_list.append(van_info[:upper_index])
    vans_scheme_list.append(van_info[:lower_index])

    middle_index = math.ceil((upper_index + lower_index) / 2)
    vans_scheme_list.append(van_info[:middle_index])

    while True:
        upper_index = middle_index
        middle_index = math.ceil((lower_index + upper_index) / 2)
        if middle_index == lower_index or middle_index == upper_index:
            break
        vans_scheme_list.append(van_info[:middle_index])
        lower_index = middle_index

        middle_index = math.ceil((lower_index + upper_index) / 2)
        if middle_index == lower_index or middle_index == upper_index:
            break
        vans_scheme_list.append(van_info[:middle_index])

    if len(vans_scheme_list) > 10:
        return vans_scheme_list[:10]

    return vans_scheme_list


def parse_worktime(time_list):
    result = []
    time_list.sort(key=lambda x: x["start"])

    for item in time_list:
        _start = pydash.get(item, "start")
        _end = pydash.get(item, "end")
        if not _start or not _end:
            continue
        _start_hour, _start_min = _start.split(":")
        _end_hour, _end_min = _end.split(":")

        start_obj = datetime.time(int(_start_hour), int(_start_min))
        end_obj = datetime.time(int(_end_hour), int(_end_min))

        result.append((start_obj, end_obj))

    return result


def parse_work_end_time(time_object, schedule_date):
    """
    time_object: list
        [{
            "description": "上班时间",
            "end": "18:00",
            "start": "08:00"
        }]
    schedule_date: datetime object
    """
    length = len(time_object)

    _start = pydash.get(time_object, f"{0}.start")
    _end = pydash.get(time_object, f"{length - 1}.end")
    if not _start or not _end:
        _start_datetime = schedule_date + datetime.timedelta(hours=8)
        _end_datetime = schedule_date + datetime.timedelta(hours=18)
        return _start_datetime, _end_datetime

    _start_hour, _start_min = _start.split(":")
    _end_hour, _end_min = _end.split(":")
    _start_datetime = schedule_date + datetime.timedelta(hours=int(_start_hour), minutes=int(_start_min))
    _end_datetime = schedule_date + datetime.timedelta(hours=int(_end_hour), minutes=int(_end_min))

    return _start_datetime, _end_datetime


def get_factory_number(factory):
    if factory == "一工厂":
        return 1
    elif factory == "二工厂":
        return 2
    elif factory == "三工厂":
        return 3

def get_all_factory_numbers():
    return (1, 2, 3)


def format_schedule(schedule_list, car_part_df, factory_name, schedule_date):
    # 整理最终排班计划表计算结果
    new_records = []
    for item in schedule_list:
        part_count = item["Parts collected"]
        logging.debug(part_count)
        logging.debug("part_count type: %s" % type(part_count))

        if isinstance(part_count, str):
            arrival_time = pydash.get(item, "Arrival time")
            arrival_time = datetime.datetime.strftime(arrival_time, "%Y-%m-%d %H:%M:%S")
            if not isinstance(arrival_time, str):
                logging.error(f"arrival_time: {arrival_time}, type: {type(arrival_time)}")
            new_records.append({
                "货车编号（牌照号）": pydash.get(item, "Van ID"),
                "物流车型": pydash.get(item, "Van size"),
                "供应商名称": pydash.get(item, "Supplier names"),
                "供应商地址": pydash.get(item, "Supplier addresses"),
                "零件编号": "",
                "零件名称": "",
                "零件数量": "",
                "箱数": "",
                "单包装容量": "",
                "包装类型": "",
                "目的地工厂": factory_name,
                "交付道口": "",
                "路程距离": pydash.get(item, "Distance travelled"),
                "装载率": "",
                "趟数": pydash.get(item, "Trip number"),
                "路程成本": pydash.get(item, "Cost"),
                "预计抵达时间": arrival_time,
            })
            continue

        is_schedule_loop = True
        for part_id, box_count in part_count.items():
            try:
                index = car_part_df.index[car_part_df["ID"] == part_id]
                part_name = car_part_df["Name"][index].tolist()[0]
                snp = car_part_df["SNP"][index].tolist()[0]
                _part_count = math.ceil(box_count / snp)
                delivery_crossings = car_part_df["Unloading crossing"][index].tolist()[0]
                packing_types = car_part_df["Packing type"][index].tolist()[0]

                arrival_time = pydash.get(item, "Arrival time")
                arrival_time = datetime.datetime.strftime(arrival_time, "%Y-%m-%d %H:%M:%S")

                _temp = {
                    "货车编号（牌照号）": pydash.get(item, "Van ID"),
                    "物流车型": pydash.get(item, "Van size"),
                    "供应商名称": pydash.get(item, "Supplier names"),
                    "供应商地址": pydash.get(item, "Supplier addresses"),
                    "零件编号": part_id,
                    "零件名称": part_name,
                    "零件数量": box_count,
                    "箱数": _part_count,
                    "单包装容量": snp,
                    "包装类型": packing_types,
                    "目的地工厂": factory_name,
                    "交付道口": delivery_crossings,
                    "路程距离": "",
                    "装载率": "",
                    "路程成本": "",
                    "趟数": pydash.get(item, "Trip number"),
                    "预计抵达时间": "",
                }
                if is_schedule_loop:
                    if not isinstance(arrival_time, str):
                        logging.error(f"arrival_time: {arrival_time}, type: {type(arrival_time)}")

                    _temp["路程成本"] = pydash.get(item, "Cost")
                    _temp["预计抵达时间"] = arrival_time
                    _temp["路程距离"] = pydash.get(item, "Distance travelled")
                    _temp["装载率"] = pydash.get(item, "Loading percentage")
                    is_schedule_loop = False
                new_records.append(_temp)
            except Exception as e:
                logging.error(f"item: {item}, part_id: {part_id} missing")
                logging.error(traceback.format_exc())
                continue
    return new_records



def  get_schedule_shift(_factory_summary_df,
                       van_info,
                       schedule_tools,
                       _schedule_start,
                       _schedule_end,
                       algorithm):
    """并行计算排班计划表
    source from Michael
    update by Chris
    """
    # Pack items by algorithm 2
    # Variables for the modified-bisection method algorithm
    # Number of parallel processes that can be run simultaneously.
    # 可以同时运行的并行进程数
    num_pars = cpu_count() if cpu_count() <= 4 else cpu_count() - 2
    # The error regarding number of vans to be chosen. Select 0 if you want exact number
    # 有关要选择的货车数量的错误。如果需要精确数字，请选择0
    van_error = 0
    lower_limit = 1  # Always set to be 1 van
    # Maximum number of vans available
    # 可用货车的最大数量
    upper_limit = len(van_info)
    # ToDo
    output4 = ""

    fn = getattr(deepcopy(schedule_tools), f"algorithm_{algorithm}", None)

    if fn is None:
        empty_df = pd.DataFrame([])
        return empty_df, empty_df, empty_df, empty_df

    # Find schedule initial upper limit
    van_info_run = van_info[:upper_limit].copy()

    alg2_schedule_df, alg2_overnight_schedule_df, alg2_late_items_df, missing_suppliers = fn(
        _factory_summary_df.copy(), van_info_run.copy(), _schedule_start, _schedule_end)

    # Check if maximum available vans is too few
    if len(alg2_late_items_df) > 0:
        return alg2_schedule_df, alg2_overnight_schedule_df, alg2_late_items_df, missing_suppliers

    # Check if minimum vans is larger than upper limit
    if lower_limit >= upper_limit:
        return alg2_schedule_df, alg2_overnight_schedule_df, alg2_late_items_df, missing_suppliers

    # --------------------------------- Modify By fux -------------------------------
    start = xftimer()
    # ---------------------------------

    # Run modified-bisection method
    # 运行修改的二分法
    while True:
        # Find all indexes to run for (the order of the list matters for later calculations)
        run_indexes = []
        for i in range(num_pars):
            index = lower_limit + (i + 1) * (upper_limit - lower_limit) / (num_pars + 1)
            run_indexes.append(int(np.ceil(index)))

        # Run across the indexes (This part is what needs to be done in parallel)
        van_info_list = []
        alg2_schedule_outputs = []
        alg2_overnightSchedule_outputs = []
        alg2_lateItems_outputs = []
        track_indexes = []

        # track_indexes = []
        # for i in run_indexes:  # RUN THIS FOR-LOOP IN PARALLEL
        #     van_info_run = van_info[:i].copy()
        #     output1, output2, output3, output4 = schedule_tools.algorithm_2(_factory_summary_df.copy(), van_info_run.copy(), _schedule_start, _schedule_end)
        #     alg2_schedule_outputs.append(output1)
        #     alg2_overnightSchedule_outputs.append(output2)
        #     alg2_lateItems_outputs.append(output3)
        #     track_indexes.append(i)
        input_track_indexes = []
        for i in run_indexes:  # RUN THIS FOR-LOOP IN PARALLEL
            van_info_run = van_info[:i].copy()
            van_info_list.append(van_info_run)
            input_track_indexes.append(i)
        current_result = create_schedule_processor(van_info_list,
                                                   _factory_summary_df,
                                                   _schedule_start,
                                                   _schedule_end,
                                                   algorithm,
                                                   deepcopy(schedule_tools),
                                                   input_track_indexes)

        for _index in run_indexes:
            logging.debug(f">>> get current_result: {current_result}")
            item = next((x for x in current_result if x["trace_index"] == _index), None)
            logging.debug(f">>> get item: {item}")
            item_schedule_outputs = pydash.get(item, "alg_schedule_df", default=pd.DataFrame([]))
            item_overnightSchedule_outputs = pydash.get(item, "alg_overnight_schedule_df", default=pd.DataFrame([]))
            item_lateItems_outputs = pydash.get(item, "alg_late_times",  default=pd.DataFrame([]))
            item_van_count = pydash.get(item, "trace_index")

            if item_van_count is None:
                continue

            logging.debug(f">>> current trace_index: {item_van_count}")

            alg2_schedule_outputs.append(item_schedule_outputs)
            alg2_overnightSchedule_outputs.append(item_overnightSchedule_outputs)
            alg2_lateItems_outputs.append(item_lateItems_outputs)
            track_indexes.append(item_van_count)

        run_indexes = track_indexes

        # Find list of indexes which deliver all car parts
        list_indexes = []
        for i in range(len(alg2_lateItems_outputs)):
            if len(alg2_lateItems_outputs[i]) == 0:
                list_indexes.append(i)

        # If list is empty, update lower limit only
        # If list is not empty, find minimum vans that will deliver all car parts then update lower and upper limit
        # Also set new schedule for updated upper limit
        if list_indexes == []:
            lower_limit = run_indexes[-1]
        else:
            for i in list_indexes:
                if run_indexes[i] < upper_limit:
                    upper_limit = run_indexes[i]
            alg2_schedule_df = alg2_schedule_outputs[track_indexes.index(upper_limit)]
            alg2_overnight_schedule_df = alg2_overnightSchedule_outputs[track_indexes.index(upper_limit)]
            alg2_late_items_df = alg2_lateItems_outputs[track_indexes.index(upper_limit)]
            for i in range(len(run_indexes)):
                if run_indexes[i] == upper_limit:
                    if i == 0:
                        # If i==0 then lower_limit does not need updating
                        pass
                    else:
                        lower_limit = run_indexes[i - 1]

        # Update error and return if tolerance is met
        error = run_indexes[1] - run_indexes[0] - 1
        if error <= van_error:
            return alg2_schedule_df, alg2_overnight_schedule_df, alg2_late_items_df, output4

        # --------------------------------- Modify By fux -------------------------------
        end = xftimer()
        running_time = end - start
        print("Running_time: " + str(running_time))
        print(lower_limit, upper_limit)

        if running_time > 180:
            print("!!! too long to wait, break")
            return alg2_schedule_df, alg2_overnight_schedule_df, alg2_late_items_df, missing_suppliers
        # ---------------------------------

class ScheduleProcess(Process):
    def __init__(self, schedule_queue, van_info, factory_summary_df, schedule_start, schedule_end, algorithm,
                 schedule_tools, _run_index):
        super(ScheduleProcess, self).__init__()
        self.van_info = van_info
        self.factory_summary_df = factory_summary_df
        self.schedule_start = schedule_start
        self.schedule_end = schedule_end
        self.algorithm = algorithm
        self.schedule_tools = schedule_tools
        self.schedule_queue = schedule_queue
        self._run_index = _run_index

    def run(self):
        proc_id = os.getpid()
        print(">>> current proc id: ", proc_id)

        fn = getattr(self.schedule_tools, f"algorithm_{self.algorithm}", None)
        if fn is None:
            return

        alg_schedule_df, alg_overnight_schedule_df, alg_late_times, missing_suppliers = fn(
            self.factory_summary_df,
            self.van_info,
            self.schedule_start,
            self.schedule_end
        )

        item = {
            "trace_index": self._run_index,
            "alg_schedule_df": alg_schedule_df,
            "alg_overnight_schedule_df": alg_overnight_schedule_df,
            "alg_late_times": alg_late_times,
            "missing_suppliers": missing_suppliers
        }
        self.schedule_queue.put(item)


def create_schedule_processor(van_info, factory_summary_df, schedule_start, schedule_end, algorithm, schedule_tools,
                              track_indexes):
    start = time.time()
    q = Queue()
    result = []

    procs = []
    # 父进程的ID和名称
    print('parent_proc_id:{0}, time: {1}'.format(os.getpid(), time.time()))

    for _vans, _tracker_index in zip(van_info, track_indexes):
        # 创建子进程
        print(len(_vans), _tracker_index)
        proc = ScheduleProcess(q, _vans, factory_summary_df, schedule_start, schedule_end, algorithm, deepcopy(schedule_tools)
                               , _tracker_index)
        procs.append(proc)
        # 启动子进程，启动一个新进程实际就是执行本进程对应的run方法
        proc.start()

    # 在join前将内容消费掉
    for proc in procs:
        while proc.is_alive():
            while True:
                try:
                    schedule_data = q.get(False)
                    if schedule_data:
                        logging.debug(f">>> get schedule result: {schedule_data}")
                        result.append(schedule_data)
                except queue.Empty:
                    break
    q.close()

    # join方法会让父进程等待子进程结束后再执行
    for proc in procs:
        proc.join()

    print("Done.")
    print("Cost: ", time.time() - start)

    return result

class SchedulerUtils(CommonUtils):
    def get_schedule(self, id):
        """
        计算调度计划表
        """
        ## 数据初始化 begin
        init_start_time = int(time.time())

        # 当天0点
        now = datetime.datetime.now()
        schedule_date = now - datetime.timedelta(hours=now.hour, minutes=now.minute, seconds=now.second, microseconds=now.microsecond)

        session = get_session()
        # 根据编号获取版本信息
        order_plan = session.query(OrderPlanModel).filter(OrderPlanModel.id == id).first()

        # 算法ID
        algorithm = order_plan.algorithm_id

        # 供应商信息地址
        cache = Cache(CacheType.SUPPLIER.value, order_plan.supplier_address_version_id)
        geocode_df = pd.read_csv(cache.get_cache())
        if geocode_df.empty:
            raise Exception('请上传供应商地址！')

        # 距离矩阵
        cache = Cache(CacheType.SUPPLIER_DISTANCE.value, order_plan.supplier_distance_version_id)
        distance_matrix_df = pd.read_csv(cache.get_cache())
        if distance_matrix_df.empty:
            raise Exception('请上传距离矩阵！')
        distance_matrix_df = distance_matrix_df.pivot(index="supplier_first_name", columns="supplier_second_name", values="distance")
        distance_matrix_df["Unit:m"] = distance_matrix_df.index
        distance_matrix_df = distance_matrix_df.reset_index()
        del distance_matrix_df["supplier_first_name"]
        distance_matrix_df.columns.name = None


        # 时间矩阵
        cache = Cache(CacheType.SUPPLIER_DURATION.value, order_plan.supplier_duration_version_id)
        time_matrix_df = pd.read_csv(cache.get_cache())
        if time_matrix_df.empty:
            raise Exception('请上传时间矩阵！')
        time_matrix_df = time_matrix_df.pivot(index="supplier_first_name", columns="supplier_second_name", values="duration")
        time_matrix_df["Unit:s"] = time_matrix_df.index
        time_matrix_df = time_matrix_df.reset_index()
        del time_matrix_df["supplier_first_name"]
        time_matrix_df.columns.name = None

        # 作业时间
        cache = Cache(CacheType.OPERATION_TIME.value, order_plan.operation_time_version_id)
        time_df = pd.read_csv(cache.get_cache())
        if time_df.empty:
            raise Exception('作业时间数据为空, 请重新上传！')

        # 工厂运转时间
        cache = Cache(CacheType.FACTORY_TRANSPORT_TIME.value, order_plan.factory_transport_time_version_id)
        availafactory_runtime_df = pd.read_csv(cache.get_cache())
        if availafactory_runtime_df.empty:
            raise Exception('厂内运行时间数据为空, 请重新上传！')

        new_loading_times = []
        for idx, data in time_df.iterrows():
            mask = (availafactory_runtime_df["work_site"] == data["work_site"])
            result = availafactory_runtime_df.loc[mask]
            if result.empty:
                new_loading_times.append({
                    "work_site": data["work_site"],
                    "work_time": data["work_time"]
                })
            else:
                _cost_time = result["transport_time"].values.tolist()[0]
                new_loading_times.append({
                    "work_site": data["work_site"],
                    "work_time": data["work_time"] + _cost_time
                })
        new_loading_df = pd.DataFrame(new_loading_times)

        # 承运商信息数据结构
        cache = Cache(CacheType.SHIPPER.value, order_plan.shipper_version_id)
        vans_df = pd.read_csv(cache.get_cache())
        if vans_df.empty:
            raise Exception('承运商数据为空, 请重新上传！')

        # 零件需求
        require_summary_ids = []
        all_require_df = []
        parts_list = session.query(OrderPlanPartsModel).filter(OrderPlanPartsModel.order_plan_id == id).all()
        for i in range(len(parts_list)):
            cache = Cache(CacheType.REQUIRE_SUMMARY.value, parts_list[i].parts_version_id)
            all_require_df.append(pd.read_csv(cache.get_cache()))
            require_summary_ids.append(parts_list[i].parts_version_id)
        summary_df = pd.concat(all_require_df)
        if summary_df.empty:
            raise Exception('零件需求汇总数据为空, 请重新计算零件需求表！')
        summary_df = summary_df.rename(columns={
            "factory_name": "工厂",
            "parts_code": "Product ID",
            "arrival_time": "Latest arrival time",
            "quantity": "Quantity",
            "supplier_name": "Supplier name",
        })
        factory_list = list(set(summary_df["工厂"].values.tolist()))


        # 库存
        stockpile1_df = stockpile2_df = stockpile3_df = None
        stockpile_list = session.query(OrderPlanInventoryModel, InventoryModel).join(InventoryModel, OrderPlanInventoryModel.inventory_version_id == InventoryModel.id).filter(OrderPlanInventoryModel.order_plan_id == id).all()
        for stockpile in stockpile_list:
            if stockpile[1].factory_id == 1:
                cache = Cache(CacheType.INVENTORY.value, stockpile[0].inventory_version_id)
                stockpile1_df = pd.read_csv(cache.get_cache())
            elif stockpile[1].factory_id == 2:
                cache = Cache(CacheType.INVENTORY.value, stockpile[0].inventory_version_id)
                stockpile2_df = pd.read_csv(cache.get_cache())
            elif stockpile[1].factory_id == 3:
                cache = Cache(CacheType.INVENTORY.value, stockpile[0].inventory_version_id)
                stockpile3_df = pd.read_csv(cache.get_cache())
            else:
                continue

        if stockpile1_df is None:
            stockpile1_df = pd.DataFrame([])
        if stockpile2_df is None:
            stockpile2_df = pd.DataFrame([])
        if stockpile3_df is None:
            stockpile3_df = pd.DataFrame([])
        stockpile_dict = {
            "一工厂": stockpile1_df,
            "二工厂": stockpile2_df,
            "三工厂": stockpile3_df,
        }

        session.close()

        init_end_time = int(time.time())
        ## 数据初始化 end

        ## 运算 begin
        cal_start_time = int(time.time())

        statistics = []
        late_items = []
        car_available_message = ""

        # 按工厂分别计算排班计划
        schedule_result_list = []
        for _factory in factory_list:
            start = time.time()
            # 筛选每个工厂的零件需求汇总 => means latest_arrival_times
            mask = (summary_df['工厂'] == _factory)
            _factory_summary_df = summary_df.loc[mask]

            _factory_number = get_factory_number(_factory)
            if _factory_number not in get_all_factory_numbers():
                continue

            # 查询工厂休息时间 TODO 获取关联排班
            result = self.find_latest_active_worktime(_factory_number, "短白班")
            if result is None:
                raise Exception(f'请先选择并设置{_factory}上班时间，如短白班，长白班，白夜班！')

            # 构造休息时间
            rest_times = pydash.get(result, "work_time.down_time")
            rest_times = parse_worktime(rest_times)

            # get work time
            _work_time = pydash.get(result, "work_time.up_time", default=[])
            _schedule_start, _schedule_end = parse_work_end_time(_work_time, schedule_date)
            logging.info(f">>> _schedule_start time: {_schedule_start}, _schedule_end: {_schedule_end}")

            ## 构建算法需要的所有必须参数
            session = get_session()
            # 零件基础信息
            require_ids = []
            all_parts_info_df = []
            require_summary_list = session.query(RequireSummaryModel).\
                filter(RequireSummaryModel.id.in_(require_summary_ids)).filter(RequireSummaryModel.factory_id == _factory_number).all()
            for i in range(len(require_summary_list)):
                require_ids.append(require_summary_list[i].weld_version_id)
                require_ids.append(require_summary_list[i].paint_version_id)
                require_ids.append(require_summary_list[i].summary_version_id)
            require_list = session.query(RequireModel).filter(RequireModel.id.in_(require_ids)).all()
            for i in range(len(require_list)):
                cache = Cache(CacheType.PARTS.value, require_list[i].parts_version_id)
                all_parts_info_df.append(pd.read_csv(cache.get_cache()))
            components_base_df = pd.concat(all_parts_info_df)
            if components_base_df.empty:
                session.close()
                raise Exception('请先运算零件需求，上传零件基础信息！')
            components_base_df = components_base_df.drop_duplicates(subset='code').reset_index()

            # 零件装配延误时间
            all_delay_df = []
            for i in range(len(require_list)):
                cache = Cache(CacheType.PARTS_LOAD_DELAY_TIME.value, require_list[i].load_delay_time_version_id)
                all_delay_df.append(pd.read_csv(cache.get_cache()))
            components_delay_df = pd.concat(all_delay_df)
            if components_delay_df.empty:
                session.close()
                raise Exception('请先运算零件需求，上传零件装配延误时间！')
            components_delay_df = components_delay_df.drop_duplicates(subset='parts_code').reset_index()

            # BOM
            all_bom_df = []
            for i in range(len(require_list)):
                cache = Cache(CacheType.BOM.value, require_list[i].bom_version_id)
                all_bom_df.append(pd.read_csv(cache.get_cache()))
            bom_df = pd.concat(all_bom_df)
            if bom_df.empty:
                session.close()
                raise Exception('请先运算零件需求，上传BOM！')
            bom_df = bom_df.drop_duplicates(subset=['car_model', 'part_code']).reset_index()

            session.close()

            # 构建算法需要的参数
            car_part_df = self.get_car_part_df(components_base_df, components_delay_df)
            car_df = self.make_car_df(bom_df, car_part_df)
            supplier_info_df = self.supplier_information_df(
                _supplier_names=geocode_df,
                loading_times=new_loading_df,
                distance_matrix_df=distance_matrix_df,
                time_matrix_df=time_matrix_df,
            )

            if car_part_df.empty or car_df.empty or supplier_info_df.empty:
                continue

            # 获取当前库存
            logging.debug(f"stockpile_dict(算法{algorithm}): {stockpile_dict}")
            logging.info(
                f"current stockpile keys: {list(stockpile_dict.keys())}, current factory: {_factory}, current alg: {algorithm}")
            stockpile_df = pydash.get(stockpile_dict, _factory)
            if stockpile_df.empty:
                stockpile_input = {}
            else:
                stockpile_input = {}
                for _car_part_id, _car_part_count in zip(stockpile_df['parts_code'], stockpile_df['parts_inventory']):
                    stockpile_input[_car_part_id] = _car_part_count

            # 根据当前库存和零件需求重新计算零件需求表
            _last_time = datetime.datetime.strptime(list(_factory_summary_df["Latest arrival time"])[-1], "%Y-%m-%d %H:%M:%S") + datetime.timedelta(minutes=1)
            logging.debug(
                f"final _time type(算法{algorithm},{_factory}): {type(_last_time)}, value: {_last_time}")
            logging.debug(f"stockpile_input(算法{algorithm}): {stockpile_input}")
            for key in stockpile_input:
                index = car_part_df.index[car_part_df["ID"] == key].tolist()[0]
                if stockpile_input[key] < car_part_df["Lower stockpile limit"][index]:
                    quantity = np.ceil(
                        (car_part_df["Lower stockpile limit"][index] - stockpile_input[key]) / car_part_df["SNP"][
                            index])

                    _new_line = {
                        "工厂": _factory,
                        "Product ID": key,
                        "Latest arrival time": str(_last_time),
                        "Quantity": quantity,
                        "Supplier name": car_part_df["Supplier"][index]
                    }

                    logging.info(
                        f"{_factory}, 算法{algorithm}, add new line in factory_summary_df : {_new_line}")
                    _factory_summary_df = _factory_summary_df.append(_new_line, ignore_index=True)

            logging.debug(f"{_factory}, 算法{algorithm}, new_factory_summary_df: {_factory_summary_df}")
            # 排班计划
            schedule_tools = routing_algorithms(car_df=car_df,
                                                car_part_df=car_part_df,
                                                supplier_information_df=supplier_info_df,
                                                distance_matrix_df=distance_matrix_df,
                                                time_matrix_df=time_matrix_df,
                                                rest_times=rest_times,
                                                factory_No=_factory_number,
                                                loading_df=new_loading_df)
            van_info = schedule_tools.give_vans_IDs(vans_df, schedule_date)
            # vans_scheme = get_input_van_scheme(van_info)
            if algorithm not in [1, 2, 3, 4]:
                continue

            alg_schedule_df, alg_overnight_schedule_df, alg_late_times, missing_suppliers = get_schedule_shift(
                _factory_summary_df,
                van_info,
                schedule_tools,
                _schedule_start,
                _schedule_end,
                algorithm
            )
            logging.debug(f"算法{algorithm} output: {alg_schedule_df}")
            if alg_schedule_df.empty:
                logging.warning("schedule result is empty...")
                continue

            alg_schedule_df = alg_schedule_df.fillna("")

            # 车辆是否充足
            if not alg_late_times.empty:
                # TODO 消息格式化
                alg_late_times["Latest arrival time"] = alg_late_times["Latest arrival time"].apply(
                    lambda x: str(x))
                alg_late_times["Scheduled delivery time"] = alg_late_times["Scheduled delivery time"].apply(
                    lambda x: str(x))
                late_items.append({
                    f"factory{_factory_number}": alg_late_times.to_dict(orient="records")
                })
                car_available_message += "{},车辆不足;\n".format(_factory)
                logging.warning("{},车辆不足;".format(late_items))

            statistic = {
                "工厂": _factory,
                "算法": algorithm,
                "总趟数": "暂未统计",
                "总路程成本": "暂未统计",
                "平均装载率": "暂未统计",
                "总车数": "暂未统计",
                "车辆充足": "充足" if alg_late_times.empty else "不充足",
                "计算耗时": "暂未统计",
                "无地理信息供应商": ",".join(list(set(missing_suppliers))),
            }

            try:
                mask = (alg_schedule_df['Parts collected'] == "") & (
                    alg_schedule_df['Supplier names'].astype(str).str.contains("工厂"))
                _filter_schedule_df = alg_schedule_df.loc[mask]
                statistic["总趟数"] = int(_filter_schedule_df["Supplier names"].count())
                statistic["总趟数"] = statistic["总趟数"] if statistic["总趟数"] else "暂未统计"
                statistic["总路程成本"] = round(float(alg_schedule_df["Cost"].sum()))
            except Exception:
                logging.error("statistic error(总趟数，总路程成本)..., factory: %s" % _factory)
                logging.error(traceback.format_exc())
            try:
                alg_average_loading_rate = 0
                last_average_loading_rate = 0
                __count = 0
                for _loading_percentage, _supplier_name in zip(alg_schedule_df['Loading percentage'],
                                                               alg_schedule_df['Supplier names']):
                    if _supplier_name == _factory:
                        alg_average_loading_rate += last_average_loading_rate
                        __count += 1
                    else:
                        last_average_loading_rate = _loading_percentage
                alg_average_loading_rate = alg_average_loading_rate / __count
                statistic["平均装载率"] = round(alg_average_loading_rate, 2)
                logging.info(f"{_factory} 装载率（算法{algorithm}）: {alg_average_loading_rate}, 趟数: {__count}")
            except Exception:
                logging.error("statistic error(平均装载率)..., factory: %s" % _factory)
                logging.error(traceback.format_exc())
            try:
                statistic["总车数"] = len(set(alg_schedule_df["Van ID"].values.tolist()))
                statistic["计算耗时"] = round(time.time() - start, 2)
            except Exception:
                logging.error("statistic error(总车数，计算耗时)..., factory: %s" % _factory)
                logging.error(traceback.format_exc())

            alg_schedule_df = alg_schedule_df.sort_values(
                by=["Van ID", "Trip number", "Loading percentage", "Arrival time"], ascending=[True, True, True, True])
            alg_schedule_content = alg_schedule_df.to_dict(orient="records")
            _temp = format_schedule(alg_schedule_content, car_part_df, _factory, schedule_date)
            schedule_result_list += _temp

            statistics.append(statistic)

        car_enough_info = list(map(lambda x: True if x["车辆充足"] == "充足" else False, statistics))
        logging.info(f">>> car_enough_info: {car_enough_info}")

        cal_end_time = int(time.time())
        ## 运算 end

        return schedule_result_list, statistics, init_end_time - init_start_time, cal_end_time - cal_start_time


class algorithm_methods:
    '''

    Description:

        This class compiles all of the methods used in object and data manipulation for the delivery schedules.

    Static methods:

        all_car_parts()

        check_stockpile()

        update_stockpile()

        dic_cars_to_list()

        pull_cars_batch()

        pull_production_line_parts()
    '''

    def __init__(self, car_df, car_part_df):
        self.car_df = car_df
        self.car_part_df = car_part_df

    # Method for finding all car parts for a given collection (dictionary) of cars
    def all_car_parts(self, cars_ID_dic):
        '''

        Inputs:

            cars_id_dic:
                A dictionary of the cars needed to be produced.
                Keys are car IDs.
                Values are number of cars.

        Outputs:

            products_dic:
                A dictionary for the products required.
                Keys are product ID.
                Values are tuple for amount of products required, size of products, packing type, workshop required at, supplier ID for product, and SNP.

        Description:

            For each car type we use car_df to find the car parts required.
            We then create a dictionary where we use car_part_df to store the number each car part required with their ID, name, size (packing dimension), packing type, workshop required at, supplier ID, and SNP.

        '''
        products_dic = {}
        for key in cars_ID_dic.keys():
            index = self.car_df.index[self.car_df["Car type"] == key].tolist()[0]
            car_parts = self.car_df["Car parts"][index]
            for item in car_parts:
                if item[0] in products_dic:
                    product_amount = products_dic[item[0]][0] + item[1]
                else:
                    product_amount = item[1]  # 如果零件号不在products_dic内，则product_amount为零件号对应的单车零件数量
                index1 = self.car_part_df.index[self.car_part_df["ID"] == item[0]].tolist()[0]
                product_size = self.car_part_df["Dimensions"][index1]  # 包装尺寸
                packing_type = self.car_part_df["Packing type"][index1]  # 包装类型
                unloading_crossing = self.car_part_df["Unloading crossing"][index1]  # 卸货道口
                supplier = self.car_part_df["Supplier"][index1]  # 供应商
                SNP = self.car_part_df["SNP"][index1]  # 装箱数量
                packing_constraint = self.car_part_df["Packing constraint"][index1]  # 是否堆叠
                arrival_time_modifier = self.car_part_df["Arrival time modifier"][index1]  # 对应装配时间
                car_part_name = self.car_part_df["Name"][index1]  # 零件名称

                products_dic[item[0]] = (
                    product_amount, product_size, packing_type, unloading_crossing, supplier, SNP, packing_constraint,
                    arrival_time_modifier, car_part_name)
        return products_dic

    # Method for checking stockpile
    @staticmethod
    def check_stockpile(products_dic, stockpile_dic):
        '''

        Inputs:

            products_dic:
                A dictionary for the products required.
                Keys are product ID.
                Values are tuple for amount of products required, size of products, packing type, workshop required at, supplier ID for product, and SNP.

            stockpile_dic
                A dictionary for the products stockpiled.
                Keys are product IDs.
                Values are number of products in stockpile.

        Outputs:

            products_dic:
                A dictionary for the products required.
                Keys are product ID.
                Values are tuple for amount of products required, size of products, packing type, workshop required at, supplier ID for product, and SNP.

            stockpile_used_dic:
                A dictionary for the products taken from the stockpile.
                Keys are product IDs.
                Values are number of products used from stockpile.

        Description:

            We remove products from the products_dic if we have them in the stockpile.
            This is done by a for-loop over the stockpile to see if there are products we already have.

        '''
        stockpile_used_dic = {}
        for product in stockpile_dic:
            if product in products_dic:
                value = products_dic[product]
                products_needed = value[0] - stockpile_dic[product]
                if products_needed <= 0:
                    # There are enough products in stockpile
                    stockpile_used_dic[product] = value[0]
                    del products_dic[product]
                else:
                    # There are not enough products in stockpile
                    stockpile_used_dic[product] = stockpile_dic[product]
                    value = list(value)
                    value[0] = products_needed
                    products_dic[product] = tuple(value)
        return products_dic, stockpile_used_dic

    # Method for updating stockpile
    @staticmethod
    def update_stockpile(stockpile_dic, stockpile_used_dic):
        '''

        '''
        updated_stockpile_dic = stockpile_dic.copy()
        for product in stockpile_used_dic:
            updated_stockpile_dic[product] += -stockpile_used_dic[product]
            if updated_stockpile_dic[product] < 0:
                print("Error in algorithm_methods.update_stockpile: used more products than exist in stockpile")
            if updated_stockpile_dic[product] <= 0:
                del updated_stockpile_dic[product]
        return updated_stockpile_dic

    # Convert dictionary of cars to list of cars
    @staticmethod
    def dic_cars_to_list(cars_dic):
        '''
        '''
        cars_list = []
        for car in cars_dic:
            for i in range(cars_dic[car]):
                cars_list.append(car)
        return cars_list

    # Create batch of cars
    @staticmethod
    def pull_cars_batch(cars_list, JPH, batch_number):
        '''
        '''
        cars_batch = {}
        for car in cars_list[(batch_number - 1) * JPH:batch_number * JPH]:  # 取JPH数值的车
            if car in cars_batch:
                cars_batch[car] += 1
            else:
                cars_batch[car] = 1
        return cars_batch

    # Take products from required position in production line
    @staticmethod
    def pull_production_line_parts(product_dic, production_lines=""):
        if production_lines == "":
            production_lines = ["Welding", "Coating", "Assembly"]
        updated_product_dic = {}
        for car_part in product_dic:
            if product_dic[car_part][3] in production_lines:
                updated_product_dic[car_part] = product_dic[car_part]
        return updated_product_dic

    # Convert parts collected to dictionary
    @staticmethod
    def convert_collected_parts_to_dic(parts_collected):
        parts_collected_dic = {}
        for part in parts_collected:
            if part in parts_collected_dic:
                parts_collected_dic[part] += 1
            else:
                parts_collected_dic[part] = 1
        return parts_collected_dic

    # Remove items from stockpile and update stockpile
    @staticmethod
    def apply_stockpile(latest_arrival_times_df, stockpile_dic):
        for i in range(len(latest_arrival_times_df)):
            car_part = latest_arrival_times_df["Product ID"][i]
            if car_part in stockpile_dic:
                latest_arrival_times_df = latest_arrival_times_df.drop(i)
                stockpile_dic[car_part] += -1
                if stockpile_dic[car_part] <= 0:
                    del stockpile_dic[car_part]
        latest_arrival_times_df = latest_arrival_times_df.reset_index()
        return latest_arrival_times_df, stockpile_dic

    # Convert parts collected to items collected
    def convert_collected_parts_to_items(self, parts_collected_dic):
        items_collected_dic = parts_collected_dic.copy()
        for car_part in items_collected_dic:
            index = self.car_part_df.index[self.car_part_df["ID"] == car_part].tolist()[0]
            items_collected_dic[car_part] = items_collected_dic[car_part] / self.car_part_df["SNP"][index]
        return items_collected_dic


class packing_algorithms:
    def __init__(self, car_part_df):
        self.car_part_df = car_part_df

    # Split items by boxes and racks
    @staticmethod
    def split_boxes_racks(supplier_products_lists):
        boxes = []
        racks = []
        for product in supplier_products_lists:
            packing_type = product[3]
            packing_constraint = product[6]
            product_id = product[4]
            dimensions = product[2]
            # logging.debug(f"arrival_time debug, type: {type(product[0])}, value: {product[0]}")
            arrival_time = datetime.datetime.strptime(product[0], "%Y-%m-%d %H:%M:%S")

            SNP = product[1]
            product_info = (product_id, dimensions, arrival_time, SNP, packing_constraint, packing_type)
            if product[3] == "料盒":  # Bin/box, to be put on trays/Frame B, tray size 1x1.2x1.2
                boxes.append(product_info)
            elif product[3] == "料架":  # Rack/Frame A
                racks.append(product_info)
            elif product[3] == "9.6M":  # Unknown
                pass
            else:
                print(product[3])
                print("Error in van_packing: Packing type not specified for product" + product)
        return boxes, racks

    # Find number of trays packed
    @staticmethod
    def find_trays(trays_packed):
        tray_list = []
        for tray in trays_packed:
            if len(tray_list) < tray[3]:
                tray_list.append([tray])
            else:
                tray_list[tray[3] - 1].append(tray)
        return tray_list

    # Pack boxes into trays and sort trays and racks by arrival time / SNP
    def pack_trays_and_sort(self, supplier_products_lists):
        supplier_racks_and_trays_lists = {}
        for supplier in supplier_products_lists:
            # Split items by boxes and racks
            boxes, racks = self.split_boxes_racks(supplier_products_lists[supplier].copy())
            # Pack trays
            trays_packed, UNUSED_OBJECT = self.bin_packing_algorithm(boxes.copy(), (1200.0, 1000.0, 1000.0))
            # Find number of trays
            tray_list = self.find_trays(trays_packed.copy())
            #  Combine racks and trays, sort by arrival time and SNP, and pack vans
            racks_and_trays = self.combine_racks_and_trays(tray_list.copy(), racks.copy())
            supplier_racks_and_trays_lists[supplier] = racks_and_trays.copy()
        return supplier_racks_and_trays_lists

    # Combine packed trays and racks
    @staticmethod
    def combine_racks_and_trays(tray_list, racks):
        racks_and_trays = racks.copy()
        for tray in tray_list:
            items = []
            arrival_time = tray[0][4]
            SNP = tray[0][5]
            constraint = "None"
            for box in tray:
                items.append((box[1], int(box[5])))
                if box[4] < arrival_time:  # version3.0.005修改
                    arrival_time = box[4]
                if SNP < box[5]:
                    SNP = box[5]
                if box[5] == "否":
                    constraint = "否"
            racks_and_trays.append((items, (1200.0, 1000.0, 1000.0), arrival_time, SNP, constraint, "料盒"))
        racks_and_trays = sorted(racks_and_trays, key=lambda x: (x[2], x[3]))
        return racks_and_trays

    # Calculate loading rate
    def loading_rate(self, van_size, parts_collected_dic):
        volume_used = 0
        van_volume = van_size[0] * van_size[1] * van_size[2]
        for car_part in parts_collected_dic:
            index = self.car_part_df.index[self.car_part_df["ID"] == car_part].tolist()[0]
            volume_used += parts_collected_dic[car_part] * self.car_part_df["Dimensions"][index][0] * \
                           self.car_part_df["Dimensions"][index][1] * self.car_part_df["Dimensions"][index][2]
        loading_percentage = volume_used / van_volume
        return np.around(loading_percentage, decimals=5)

    # Method for checking if item fits in space
    @staticmethod
    def does_item_fit(item, space_size):
        '''
        Inputs:
            item:
                A tuple for the objects dimensions (length, width, height).
                Length and width are interchangeable, but height is not.

            space_size:
                A tuple for the dimensions of the to fit the object into (length, width, height).
                Length and width are interchangeable, but height is not.
        Outputs:
            (boolean, int):
                boolean: Indicates whether item can fit into space. True indicates it can fit, False indicates it cannot.
                int: The orientation of the item. If 0, then box is not rotated, but if 1 the box is rotated 90 degrees.
        Description:

            For a given cuboid item and space, we find whether or not the object will fit.
            We check whether the objects dimensions are smaller than the spaces before and after rotating.
            If object fits we return true, otherwise false.
            We output 0 if object is not rotated and 1 otherwise.
        '''
        # Check if height fits.
        if item[2] > space_size[2]:  # If item height is too large, return false.
            return (False, 0)
        else:
            # Check if length fits.
            if item[0] > space_size[0]:
                # Rotate object.
                if item[0] > space_size[1]:
                    return (False, 0)  # If item length is larger than length and width of space, return false.
                elif item[1] > space_size[0]:
                    return (False, 0)  # If item does not fit after rotation, return false.
                else:
                    return (True, 1)  # Else, item fits after rotation.
            elif item[1] > space_size[1]:
                # Length fits: don't rotate.
                if item[1] > space_size[0]:
                    return (False, 0)  # If item width is larger than length and width of space, return false.
                elif item[0] > space_size[1]:
                    return (False, 0)  # If item does not fit after rotation, return false.
                else:
                    return (True, 1)  # Else, item fits after rotation.
            else:
                return (True, 0)  # Item fits without rotation.

    # Method for placing item in bin
    @staticmethod
    def place_item_in_bin(item, space_size):
        '''

        Inputs:

            item:
                A tuple for the objects dimensions (length, width, height).
                Length and width are interchangeable, but height is not.

            space_size:
                A tuple for the dimensions of the to fit the object into (length, width, height).
                Length and width are interchangeable, but height is not.

        Outputs:

            new_spaces:
                A list of tuples for the spaces left over after the object has been placed into the space.
                Tuples are for the objects dimensions (length, width, height) and the position of the space relative to the object placed.

        Description:

            A list of spaces for the space left after the item is placed is created.
            The spaces on top, in front, and beside the object make three cuboid spaces, each of which are appended to a list for output.

        '''
        # Find space available above object
        top_space = (item[0], item[1], space_size[2] - item[2], "Top")
        # Find space available in front of the object
        front_space = (space_size[0] - item[0], space_size[1], space_size[2], "Front")
        # Find space available to the side of the object
        side_space = (item[0], space_size[1] - item[1], space_size[2], "Side")
        # Remove spaces that are empty
        new_spaces = []
        spaces = [top_space, front_space, side_space]
        for space in spaces:
            if any([space[0] < 0, space[1] < 0, space[2] < 0]):
                print("Error in place_item_in_bin: length is negative")
            elif all([space[0] > 0, space[1] > 0, space[2] > 0]):
                new_spaces.append(space)
        return new_spaces

    # Check constraint
    @staticmethod
    def check_constraint(packing_type, item_constraint, space_constraint):
        '''

        '''
        if space_constraint == "None":
            return True
        else:
            if item_constraint == "否":
                if packing_type == space_constraint:
                    return True
                else:
                    return False
            else:
                return True

    # The bin packing algorithm
    def bin_packing_algorithm(self, item_list, bin_size, max_bins=np.inf, max_layer=3, spaces="None"):
        '''

        Inputs:

            item_list:
                A list of items to be placed into objects.
                Each element is a list containing the following information for the item to be placed:
                Object ID, object size,  object SNP.

            bin_size:
                A tuple for the bin (trays/vans) dimensions (length, width, height).

            bin_amount:
                Float/int for number of available bins (trays/vans).

            max_layer:
                Float/int for maximum number of objects which can be placed on top of each other.

        Outputs:

            trays_packed:
                List of trays/vans packed with items.
                Each element is a list containing the following information for tray packed:
                Item size, item ID, height position (number of objects below it), tray number, arrival time, item SNP, constraint type, packing type.

        Description:

            This method packs objects (item_list) into bins (trays/vans).
            The algorithm begins by defining the number of bins (to track when the maximum number of bins has been reached) and the set of initial available spaces (a single tray/van which is empty and of size bin_size).
            For loop runs through the items and places them in the bins (if possible).
            First, we check if the item can fit in the bin.
            If the item fits, we rotate it if necessary, and update the list of spaces by adding a space with the bin ("None" becomes item ID), and then adding the spaces left over from the bin.
            If maximum number of items stacked on top of each other is reached, the space above the item is not appended to the list.
            If there is no space for the object, we append another bin (tray/van) to the list (where the object is then placed) if the maximum number of bins is not reached.
            We end by only accounting for spaces which contain objects.

        '''
        number_bins = 1
        if spaces == "None":
            spaces = [[bin_size, "None", 1, 1, "None", "None", "None", "None"]]

        for item in item_list:
            item_id = item[0]
            item_size = item[1]
            item_arrival_time = item[2]
            item_SNP = item[3]
            for space in spaces:
                if space[1] == "None":
                    does_fit = self.does_item_fit(item_size, space[0])
                    if self.check_constraint(item[5], item[4], space[6]):
                        pass
                    else:
                        does_fit = (False, does_fit[1])  # Python元组为不可更改对象，不能对其直接赋值，所以重新构造了新的元组
                    if does_fit[0]:
                        if does_fit[1] == 1:
                            item_size = (item_size[1], item_size[0], item_size[2])
                        old_space = spaces[spaces.index(space)]
                        new_space = [item_size, item_id, old_space[2], space[3], item_arrival_time, item_SNP]
                        spaces[spaces.index(space)] = new_space
                        new_spaces = self.place_item_in_bin(item_size, space[0])
                        for space_ in new_spaces:
                            if space_[3] == "Top":
                                if space[2] + 1 <= max_layer:
                                    if space[6] != "None":
                                        constraint = space[6]
                                    elif item[5] == "否":
                                        constraint = item[4]
                                    else:
                                        constraint = "None"
                                    spaces.append(
                                        [space_[:3], "None", space[2] + 1, space[3], "None", "None", constraint,
                                         "None"])
                            else:
                                spaces.append([space_[:3], "None", space[2], space[3], "None", "None", "None", "None"])
                        break

                if space == spaces[-1]:
                    if number_bins >= max_bins:
                        continue
                    else:
                        spaces.append([bin_size, "None", 1, number_bins + 1, "None", "None", "None", "None"])
                        number_bins += 1

        trays_packed = []
        space_left = []
        for space in spaces:
            if space[1] == "None":
                space_left.append(space)
            else:
                trays_packed.append(space)
        return trays_packed, space_left


class routing_algorithms:
    '''

    Description:

        This class compiles all of the methods used for the routing algorithm.

    Methods:



    '''

    def __init__(self, car_df, car_part_df, supplier_information_df, distance_matrix_df,
                 time_matrix_df, rest_times, factory_No, loading_df):
        """
        car_df: 汽车表
        car_part_df: 汽车零件表
        supplier_information_df: 供应商信息表
        distance_matrix_df: 距离信息表
        time_matrix_df: 时间信息表
        rest_times: 休息时间表
        factory_No: 工厂
        loading_df: 零件延误信息表
        stockpile_df: 现有库存表
        """
        self.car_part_df = car_part_df
        self.supplier_information_df = supplier_information_df
        self.distance_matrix_df = distance_matrix_df
        self.time_matrix_df = time_matrix_df
        self.rest_times = rest_times
        self.factory_No = factory_No
        self.factoryLoadingTimes_df = loading_df

        self.packing_algorithms = packing_algorithms(car_part_df)
        self.algorithm_methods = algorithm_methods(car_df, car_part_df)
        self.car_is_cal_solid_cost_list = []

    # Give vans IDs
    @staticmethod
    def give_vans_IDs(vans_df, schedule_date):
        '''

        '''
        van_info = []
        for i in range(len(vans_df)):
            van_id = vans_df["van_code"][i]
            size = (vans_df["carriage_length"][i] * 1000, vans_df["carriage_width"][i] * 1000, vans_df["carriage_height"][i] * 1000)
            current_trip_number = 0
            # update in version v3.0.010
            next_arrival_time = datetime.datetime.combine(schedule_date.date(),
                                                          datetime.time(hour=0, minute=0, second=0))
            cost_modifier = vans_df["daily_fixed_cost"][i]
            cost_proportion = vans_df["operating_costs"][i]
            day = 1  # update in version v3.0.005
            van_info.append((van_id, size, current_trip_number, next_arrival_time, cost_modifier, cost_proportion, day))
        return van_info

    # 根据路程时间获取供货商线路字典
    # @staticmethod
    # def get_supplier_line_dict_by_distance(time_matrix_df):
    #     time_matrix_df = time_matrix_df.set_index('Unit:s')
    #     time_matrix_df = time_matrix_df.drop('一工厂', axis=1, errors='ignore').drop('一工厂', axis=0, errors='ignore')
    #     time_matrix_df = time_matrix_df.drop('二工厂', axis=1, errors='ignore').drop('二工厂', axis=0, errors='ignore')
    #     time_matrix_df = time_matrix_df.drop('三工厂', axis=1, errors='ignore').drop('三工厂', axis=0, errors='ignore')
    #
    #     return pd.DataFrame(np.take(time_matrix_df.columns, np.argsort(time_matrix_df, axis=1).iloc[:, 1:]).T, index=time_matrix_df.index).T.to_dict('l')

    # Split car parts by supplier
    def split_parts_by_supplier(self, latest_arrival_time_df):
        supplier_products_lists = {}
        for i in latest_arrival_time_df.index.values.tolist():
            supplier_name = latest_arrival_time_df["Supplier name"][i]
            quantity = int(latest_arrival_time_df["Quantity"][i])
            quantity_ = quantity
            latest_arrival_time = latest_arrival_time_df["Latest arrival time"][i]
            product_id = latest_arrival_time_df["Product ID"][i]
            try:
                index = self.car_part_df.index[self.car_part_df["ID"] == product_id].tolist()[0]
            except:
                continue
            if supplier_name in supplier_products_lists:
                for j in range(len(supplier_products_lists[supplier_name])):
                    if supplier_products_lists[supplier_name][len(supplier_products_lists[supplier_name]) - j - 1][
                        4] == product_id:
                        quantity += - \
                            supplier_products_lists[supplier_name][len(supplier_products_lists[supplier_name]) - j - 1][
                                5]
                        # version 9 update
                        supplier_products_lists[supplier_name][len(supplier_products_lists[supplier_name]) - j - 1][
                            5] += - quantity_
                        if supplier_products_lists[supplier_name][len(supplier_products_lists[supplier_name]) - j - 1][
                            5] < 0:
                            supplier_products_lists[supplier_name][len(supplier_products_lists[supplier_name]) - j - 1][
                                5] = 0
                        break
            SNP = self.car_part_df["SNP"][index]
            size = self.car_part_df["Dimensions"][index]
            package_type = self.car_part_df["Packing type"][index]
            package_constraint = self.car_part_df["Packing constraint"][index]
            units_to_buy = int(np.ceil(quantity / SNP))
            extra_ordered = int(units_to_buy * SNP - quantity)
            product_info = [latest_arrival_time, SNP, size, package_type, product_id, extra_ordered, package_constraint]
            for k in range(units_to_buy):
                if supplier_name in supplier_products_lists:
                    product_list = supplier_products_lists[supplier_name]
                    product_list.append(product_info)
                    supplier_products_lists[supplier_name] = product_list
                else:
                    supplier_products_lists[supplier_name] = [product_info]
        return supplier_products_lists

    # Create products list
    def create_products_lists(self, latest_arrival_time_df, i):
        supplier = latest_arrival_time_df["Supplier name"][i]
        latest_arrival_time = latest_arrival_time_df["Latest arrival time"][i]
        product_ID = latest_arrival_time_df["Product ID"][i]
        quantity = latest_arrival_time_df["Quantity"][i]
        index = self.car_part_df.index[self.car_part_df["ID"] == product_ID].tolist()[0]
        SNP = self.car_part_df["SNP"][index]
        size = self.car_part_df["Dimensions"][index]
        package_type = self.car_part_df["Packing type"][index]
        package_constraint = self.car_part_df["Packing constraint"][index]
        units_to_buy = int(np.ceil(quantity / SNP))
        extra_ordered = int(units_to_buy * SNP - quantity)
        product_list = []
        for j in range(units_to_buy):
            product_list.append(
                [latest_arrival_time, SNP, size, package_type, product_ID, extra_ordered, package_constraint])
        supplier_products_lists = {supplier: product_list}
        return supplier_products_lists

    # Find earliest time for products to arrive
    @staticmethod
    def find_earliest_date(supplier_racks_and_trays_lists):
        earliest_date = supplier_racks_and_trays_lists[list(supplier_racks_and_trays_lists.keys())[0]][0][2]
        for supplier in supplier_racks_and_trays_lists:
            for product in supplier_racks_and_trays_lists[supplier]:
                if product[2] < earliest_date:
                    earliest_date = product[2]
        return earliest_date

    # Find list of suppliers which have products next needed (by latest arrival time)
    @staticmethod
    def find_supplier_list(supplier_racks_and_trays_lists, earliest_date, hours=2):
        supplier_list = []
        for supplier in supplier_racks_and_trays_lists:
            for product in supplier_racks_and_trays_lists[supplier]:
                if product[2] < earliest_date + datetime.timedelta(hours=hours):
                    supplier_list.append(supplier)
                    break
        return supplier_list

    # Find supplier info
    def find_supplier_information(self, supplier_name, factory_No):
        distance = ""
        travel_time = ""

        try:

            index = \
                self.supplier_information_df.index[self.supplier_information_df["Supplier name"] == supplier_name].tolist()[
                    0]
        except IndexError:
            raise Exception(f"未找到供应商: {supplier_name}, 请更新供应商地址信息")
        supplier_address = self.supplier_information_df["Address"][index]
        loading_time = float(self.supplier_information_df["Loading time"][index]) * 60
        # Find distance to supplier (and add unloading time to travel time)
        if factory_No == 1:
            distance = self.supplier_information_df["Distance (first factory)"][index]
            travel_time = datetime.timedelta(
                seconds=int(self.supplier_information_df["Travel time (first factory)"][index]) + loading_time)
        elif factory_No == 2:
            distance = self.supplier_information_df["Distance (second factory)"][index]
            travel_time = datetime.timedelta(
                seconds=int(self.supplier_information_df["Travel time (second factory)"][index]) + loading_time)
        elif factory_No == 3:
            distance = self.supplier_information_df["Distance (third factory)"][index]
            travel_time = datetime.timedelta(
                seconds=int(self.supplier_information_df["Travel time (third factory)"][index]) + loading_time)
        else:
            print("Undefined factory number provided.")
        return supplier_address, distance, travel_time

    def find_supplier_information_home(self, supplier_name, factory_No, crossings):
        distance = None
        travel_time = None

        index = \
            self.supplier_information_df.index[self.supplier_information_df["Supplier name"] == supplier_name].tolist()[
                0]
        supplier_address = self.supplier_information_df["Address"][index]
        loading_time = 0
        for crossing in crossings:
            try:
                workSite = self.factoryLoadingTimes_df["work_site"]
                index = self.factoryLoadingTimes_df.index[workSite == str(crossing)].tolist()[0]
                loading_time += float(self.factoryLoadingTimes_df["work_time"][index]) * 60
            except Exception:
                logging.warning("No loading time found for crossing: " + str(crossing) + "号卸货道口")
                logging.warning(traceback.format_exc())

        # Find distance to supplier (and add unloading time to travel time)
        if factory_No == 1:
            distance = self.supplier_information_df["Distance (first factory)"][index]
            travel_time = datetime.timedelta(
                seconds=int(self.supplier_information_df["Travel time (first factory)"][index]) + loading_time)
        elif factory_No == 2:
            distance = self.supplier_information_df["Distance (second factory)"][index]
            travel_time = datetime.timedelta(
                seconds=int(self.supplier_information_df["Travel time (second factory)"][index]) + loading_time)
        elif factory_No == 3:
            distance = self.supplier_information_df["Distance (third factory)"][index]
            travel_time = datetime.timedelta(
                seconds=int(self.supplier_information_df["Travel time (third factory)"][index]) + loading_time)
        else:
            logging.warning("find_supplier_information_home funcs: Undefined factory number provided.")

        return supplier_address, distance, travel_time

    # Find supplier info
    def find_supplier_distances(self, supplier_name, destination):
        flag = True

        index = \
            self.supplier_information_df.index[self.supplier_information_df["Supplier name"] == supplier_name].tolist()[
                0]
        supplier_address = self.supplier_information_df["Address"][index]
        loading_time = float(self.supplier_information_df["Loading time"][index]) * 60
        # Find distance to destination (and add unloading time to travel time)
        try:
            index = self.distance_matrix_df.index[self.distance_matrix_df["Unit:m"] == supplier_name].tolist()[0]
            distance = self.distance_matrix_df[destination][index]
        except:
            logging.warning(
                "find_supplier_distances funcs: No distance found for supplier: " + supplier_name)
            logging.warning(traceback.format_exc())
            if isinstance(self.distance_matrix_df, pd.DataFrame):
                logging.warning(self.distance_matrix_df.columns)
            distance = 10000
            flag = False
        try:
            index = self.time_matrix_df.index[self.time_matrix_df["Unit:s"] == supplier_name].tolist()[0]
            travel_time = datetime.timedelta(seconds=int(self.time_matrix_df[destination][index]) + loading_time)
        except:
            logging.warning(
                "find_supplier_distances funcs: No travel time found for supplier: " + supplier_name)
            logging.warning(traceback.format_exc())
            travel_time = datetime.timedelta(seconds=1500 + loading_time)
            if isinstance(self.time_matrix_df, pd.DataFrame):
                logging.warning(self.time_matrix_df.columns)
            flag = False
        return supplier_address, distance, travel_time, flag

    # Find car parts to be collected
    @staticmethod
    def find_collected_parts(van_list):
        '''

        '''
        parts_collected = []
        for van in van_list:
            for product in van:
                if isinstance(product[1], list):
                    for item in product[1]:
                        for i in range(item[1]):
                            parts_collected.append(item[0])
                else:
                    for i in range(int(product[5])):
                        parts_collected.append(product[1])
        return parts_collected

    # Find number of vans
    @staticmethod
    def find_number_vans(vans_packed):
        van_list = []
        for van in vans_packed:
            if len(van_list) < van[3]:
                van_list.append([van])
            else:
                van_list[van[3] - 1].append(van)
        return van_list

    # Rank suppliers by latest arrival time then largest amount of car parts to be collected
    @staticmethod
    def order_suppliers_by_volume_of_items(supplier_list, supplier_racks_and_trays_lists):
        '''

        '''
        new_supplier_list = []
        for supplier in supplier_list:
            volume = 0
            for car_part in supplier_racks_and_trays_lists[supplier]:
                volume += car_part[1][0] * car_part[1][1] * car_part[1][2]
            new_supplier_list.append((supplier, volume))
        new_supplier_list = sorted(new_supplier_list, key=lambda x: x[1])
        supplier_list = []
        for item in new_supplier_list:
            supplier_list.append(item[0])
        return supplier_list

    # Rank suppliers by largest amount of car parts to be collected counting earliest arrival date only
    @staticmethod
    def order_suppliers_by_volume_of_items2(supplier_list, supplier_racks_and_trays_lists):
        '''

        '''
        earliest_date = routing_algorithms.find_earliest_date(supplier_racks_and_trays_lists)
        new_supplier_list = []
        for supplier in supplier_list:
            volume = 0
            for car_part in supplier_racks_and_trays_lists[supplier]:
                if car_part[2] == earliest_date:
                    volume += car_part[1][0] * car_part[1][1] * car_part[1][2]
            new_supplier_list.append((supplier, volume))
        new_supplier_list = sorted(new_supplier_list, key=lambda x: x[1])
        supplier_list = []
        for item in new_supplier_list:
            supplier_list.append(item[0])
        return supplier_list

    # Rank suppliers by largest amount of car parts to be collected counting earliest arrival date only
    def order_suppliers_by_distance(self, supplier_list, supplier_racks_and_trays_lists):
        '''

        '''
        earliest_date = routing_algorithms.find_earliest_date(supplier_racks_and_trays_lists)
        new_supplier_list = []
        for supplier in supplier_list:
            try:
                travel_time = self.time_matrix_df[supplier][0]
            except:
                travel_time = 1500
            new_supplier_list.append((supplier, travel_time))
        new_supplier_list = sorted(new_supplier_list, key=lambda x: x[1])
        supplier_list = []
        for item in new_supplier_list:
            supplier_list.append(item[0])
        return supplier_list

    # Rank suppliers by latest arrival time then distance from factory
    def order_suppliers_by_minimal_total_travel_time(self, current_supplier_name, supplier_list):
        '''

        '''
        # Remove current supplier from list of suppliers
        supplier_list.remove(current_supplier_name)
        # Find current supplier name from ID
        times = []
        for supplier in supplier_list:
            # Find supplier name from ID
            try:
                index = self.time_matrix_df.index[self.time_matrix_df["Unit:s"] == current_supplier_name].tolist()[0]
                # Find travel time between current supplier and supplier, and then add time to travel back to factory
                time = self.time_matrix_df[supplier][index] + self.time_matrix_df[supplier][0]
            except:
                time = 1500
            times.append([time, supplier])
        times = sorted(times, key=lambda x: x[0])
        return times[0][1]

    # Find supplier with most items at most recent time by volume
    def find_supplier_most_item_volume(self, latest_arrival_time_df):
        '''

        '''
        supplier_volume_dic = {}
        earliest_time = latest_arrival_time_df["Latest arrival time"].tolist()[0]
        for i in latest_arrival_time_df.index.tolist():
            if latest_arrival_time_df["Latest arrival time"][i] != earliest_time:
                break
            supplier = latest_arrival_time_df["Supplier name"][i]
            product_ID = latest_arrival_time_df["Product ID"][i]
            index = self.car_part_df.index[self.car_part_df["ID"] == product_ID].tolist()[0]
            product_volume = self.car_part_df["Dimensions"][index][0] * self.car_part_df["Dimensions"][index][1] * \
                             self.car_part_df["Dimensions"][index][2]
            if supplier in supplier_volume_dic:
                supplier_volume_dic[supplier] += latest_arrival_time_df["Quantity"][i] * product_volume
            else:
                supplier_volume_dic[supplier] = latest_arrival_time_df["Quantity"][i] * product_volume
        volume = 0
        supplier_name = "None"
        for supplier in supplier_volume_dic:
            if supplier_volume_dic[supplier] > volume:
                volume = supplier_volume_dic[supplier]
                supplier_name = supplier
        return supplier_name, earliest_time

    # Organise trip
    def organise_trip(self, supplier, factory_No, van_info, rest_times, supplier_racks_and_trays_lists, schedule_date,
                      spaces="None", hours=2):
        '''

        '''

        # Find supplier info
        supplier_address, distance, travel_time = self.find_supplier_information(supplier, factory_No)

        # Organise trip and update van info
        trip_info = list(van_info[0])
        trip_number = trip_info[2] + 1
        trip_info[2] = trip_number
        if trip_number == 1:
            arrival_time = schedule_date
        else:
            arrival_time = trip_info[3] + travel_time
        for rest_time in rest_times:
            if all([arrival_time.time() > rest_time[0], arrival_time.time() < rest_time[1]]):
                arrival_time = datetime.datetime.combine(arrival_time.date(), rest_time[1])
        travel_time = (datetime.datetime.combine(datetime.date(1, 1, 1),
                                                 datetime.time(hour=0, minute=0, second=0)) + travel_time).time()
        van_ID = trip_info[0]
        van_size = trip_info[1]
        trip_info[3] = arrival_time
        # 判断该卡车是否已经在计算车辆每日固定成本，如果没有，则计算，如果已经计算过，则不需要再计算
        if van_ID in self.car_is_cal_solid_cost_list:
            cost = distance / 1000 * van_info[0][5]
        else:
            cost = van_info[0][4] + distance / 1000 * van_info[0][5]
            self.car_is_cal_solid_cost_list.append(van_ID)
        van_info[0] = tuple(trip_info)

        # Find index at which car parts are required for more than 2 hours from arrival time
        index = 0
        time1 = supplier_racks_and_trays_lists[supplier][0][2] + datetime.timedelta(hours=hours)
        for i in range(len(supplier_racks_and_trays_lists[supplier])):
            index += 1
            if supplier_racks_and_trays_lists[supplier][i][2] > time1:
                break

        # Pack van
        vans_packed, space_left = self.packing_algorithms.bin_packing_algorithm(
            supplier_racks_and_trays_lists[supplier][:index], van_size, spaces=spaces, max_bins=1)

        # update by version 3.0.011
        # Latest arrival time
        if len(vans_packed) > 0:
            latest_arrival_time = vans_packed[0][-2]
        else:
            latest_arrival_time = " "

        # Find number of vans
        van_list = routing_algorithms.find_number_vans(vans_packed)

        # Find car parts to be collected
        parts_collected = routing_algorithms.find_collected_parts(van_list)

        # Convert parts collected to dictionary
        parts_collected_dic = self.algorithm_methods.convert_collected_parts_to_dic(parts_collected)

        # Convert parts collected to items collected (by SNP)
        items_collected_dic = self.algorithm_methods.convert_collected_parts_to_items(parts_collected_dic)

        # Calculate loading rate
        loading_percentage = self.packing_algorithms.loading_rate(van_size, items_collected_dic)

        # Update supplier list and make list of late parts
        descriptions_list = []
        late_parts_list = []
        scheduled_times_late_list = []
        latest_times_late_list = []
        list_of_parts = supplier_racks_and_trays_lists[supplier].copy()

        if len(van_list) > 0:
            for car_part in van_list[0]:
                for i in range(len(list_of_parts)):
                    if car_part[1] == list_of_parts[i][0]:
                        if list_of_parts[i][2] < arrival_time:
                            late_parts_list.append(list_of_parts[i][0])
                            scheduled_times_late_list.append(arrival_time)
                            latest_times_late_list.append(list_of_parts[i][2])  # update in version 3.0.005
                            if isinstance(list_of_parts[i][0], list):
                                descriptions_list.append("Some parts in tray are late.")
                            else:
                                descriptions_list.append("Late")
                        list_of_parts.pop(i)
                        supplier_racks_and_trays_lists[supplier] = list_of_parts
                        break

        # Remove supplier if no products left
        if len(supplier_racks_and_trays_lists[supplier]) <= 0:
            del supplier_racks_and_trays_lists[supplier]

        return van_info, supplier_address, distance, travel_time, supplier_racks_and_trays_lists, cost, space_left, parts_collected_dic, loading_percentage, van_ID, van_size, trip_number, arrival_time, late_parts_list, scheduled_times_late_list, latest_times_late_list, descriptions_list, space_left, latest_arrival_time

    def algorithm_1(self, latest_arrival_time_df, van_info, schedule_date, schedule_end_date):
        '''

        '''
        missing_suppliers = []
        late_parts_list = []
        scheduled_times_late_list = []
        latest_times_late_list = []
        descriptions_list = []
        # Split car parts by supplier
        supplier_products_lists = self.split_parts_by_supplier(latest_arrival_time_df.copy())

        # Pack boxes into trays and sort trays and racks by arrival time / SNP
        supplier_racks_and_trays_lists = self.packing_algorithms.pack_trays_and_sort(supplier_products_lists)

        # Organise trips
        van_IDs_list = []
        van_sizes_list = []
        trip_numbers_list = []
        number_suppliers_visited = []
        arrival_times_list = []
        travel_times_list = []
        suppliers_list = []
        costs_list = []
        distances_list = []
        parts_collected_list = []
        supplier_addresses_list = []
        loading_percentages_list = []
        list_stockpile_changes = []
        list_part_arrival_times = []
        latest_arrival_times_list = []

        while len(supplier_racks_and_trays_lists) > 0:

            # Find earliest time for products to arrive
            earliest_date = routing_algorithms.find_earliest_date(supplier_racks_and_trays_lists)

            # Find list of suppliers which have products next needed (by latest arrival time)
            hours = 24
            supplier_list = routing_algorithms.find_supplier_list(supplier_racks_and_trays_lists, earliest_date,
                                                                  hours=hours)

            # Order suppliers by volume of items
            supplier_list = routing_algorithms.order_suppliers_by_volume_of_items(supplier_list,
                                                                                  supplier_racks_and_trays_lists)

            # Choose first supplier
            supplier = supplier_list[0]

            # Sort vans
            van_info = sorted(van_info, key=lambda x: (x[6], x[3]))
            previous_arrival_time = van_info[0][3]

            # Perform trip
            van_info, supplier_address, distance, travel_time, supplier_racks_and_trays_lists, cost, space_left, parts_collected_dic, loading_percentage, van_ID, van_size, trip_number, arrival_time, late_parts_list, scheduled_times_late_list, latest_times_late_list, descriptions_list, space_left, latest_arrival_time = self.organise_trip(
                supplier, self.factory_No, van_info, self.rest_times, supplier_racks_and_trays_lists, schedule_date,
                hours=hours)

            if len(parts_collected_dic) == 0:
                continue

            # Append trip
            van_IDs_list.append(van_ID)
            van_sizes_list.append(van_size)
            trip_numbers_list.append(trip_number)
            arrival_times_list.append(arrival_time)
            travel_times_list.append(travel_time)
            suppliers_list.append(supplier)
            costs_list.append(cost)
            distances_list.append(distance)
            parts_collected_list.append(parts_collected_dic)
            supplier_addresses_list.append(supplier_address)
            loading_percentages_list.append(loading_percentage)
            latest_arrival_times_list.append(" ")

            # Add factory crossings to visit
            crossings = []
            for part in parts_collected_dic:
                index = self.car_part_df.index[self.car_part_df["ID"] == part].tolist()[0]
                crossing = self.car_part_df["Unloading crossing"][index]
                if crossing not in crossings:
                    crossings.append(crossing)

            # Return to factory
            supplier_address, distance, travel_time = self.find_supplier_information_home(supplier, self.factory_No,
                                                                                          crossings)
            arrival_time = arrival_times_list[-1] + travel_time
            travel_time = (datetime.datetime.min + travel_time).time()
            # 因为返回工厂 所以不需要计算cost
            if van_ID in self.car_is_cal_solid_cost_list:
                cost = distance / 1000 * van_info[0][5]
            else:
                cost = van_info[0][4] + distance / 1000 * van_info[0][5]
                self.car_is_cal_solid_cost_list.append(van_ID)
            parts_collected_dic = ""
            if self.factory_No == 1:
                supplier = "一工厂"
            elif self.factory_No == 2:
                supplier = "二工厂"
            elif self.factory_No == 3:
                supplier = "三工厂"
            else:
                supplier = "未知工厂"
            supplier_address = "重庆市江北区两江大道233号"
            supplier_coordinate = "106.762841,29.632332"
            loading_percentage = " "

            # Append trip
            van_IDs_list.append(van_ID)
            van_sizes_list.append(van_size)
            trip_numbers_list.append(trip_number)
            arrival_times_list.append(arrival_time)
            travel_times_list.append(travel_time)
            suppliers_list.append(supplier)
            costs_list.append(cost)
            distances_list.append(distance)
            parts_collected_list.append(parts_collected_dic)
            supplier_addresses_list.append(supplier_address)
            loading_percentages_list.append(loading_percentage)
            latest_arrival_times_list.append(latest_arrival_time)

            # Check trip has passed till next day
            if arrival_time < previous_arrival_time:
                trip_info = list(van_info[0])
                trip_info[6] += 1
                van_info[0] = tuple(trip_info)

            # Change trip times for first trip
            if trip_number == 1:
                list_length = len(van_IDs_list)
                arrival_times_list[-1] = schedule_date
                for i in range(1):
                    travel_time = datetime.datetime.combine(datetime.datetime.min,
                                                            travel_times_list[-i - 1]) - datetime.datetime.min
                    arrival_times_list[-i - 2] = arrival_times_list[-i - 1] - travel_time

            # Remove van if this was its final trip
            if trip_number > 3:
                van_info.pop(0)

            # Append all items to late list if there are no more vans
            if len(van_info) > 0:
                pass
            else:
                if len(supplier_racks_and_trays_lists) > 0:
                    list_of_parts = supplier_racks_and_trays_lists.copy()
                    description = "车辆不足"
                    scheduled_time = " "
                    for supplier in list_of_parts:
                        for i in range(len(list_of_parts[supplier])):
                            late_parts_list.append(list_of_parts[supplier][i][0])
                            latest_times_late_list.append(list_of_parts[supplier][i][2])
                            scheduled_times_late_list.append(scheduled_time)
                            descriptions_list.append(description)
                    supplier_racks_and_trays_lists = {}

        # Produce dataframe (main output)
        schedule_df = pd.DataFrame(
            {"Van ID": van_IDs_list, "Supplier names": suppliers_list, "Arrival time": arrival_times_list,
             "Latest arrival time": latest_arrival_times_list, "Travel/loading time": travel_times_list,
             "Van size": van_sizes_list, "Parts collected": parts_collected_list, "Trip number": trip_numbers_list,
             "Cost": costs_list, "Distance travelled": distances_list, "Supplier addresses": supplier_addresses_list,
             "Loading percentage": loading_percentages_list})

        # Produce overdate schedule
        van_IDs_list_late = []
        van_sizes_list_late = []
        trip_numbers_list_late = []
        arrival_times_list_late = []
        travel_times_list_late = []
        suppliers_list_late = []
        costs_list_late = []
        distances_list_late = []
        parts_collected_list_late = []
        supplier_addresses_list_late = []
        loading_percentages_list_late = []
        latest_arrival_times_list_late = []  # update in version v3.0.011
        index = 0

        index_list = []
        while index < len(schedule_df) - 1:
            current_van_id = schedule_df["Van ID"][index]
            current_trip_number = schedule_df["Trip number"][index]
            max_index = index
            for i in range(index, len(schedule_df)):
                max_index = i
                if all([schedule_df["Van ID"][i] == current_van_id,
                        schedule_df["Trip number"][i] == current_trip_number]):
                    arrival_time = schedule_df["Arrival time"][i]
                else:
                    break
            if arrival_time > schedule_end_date:
                for i in range(index, max_index):
                    index_list.append(i)

                    van_ID = schedule_df["Van ID"][i]
                    van_size = schedule_df["Van size"][i]
                    trip_number = schedule_df["Trip number"][i]
                    arrival_time = schedule_df["Arrival time"][i]
                    travel_time = schedule_df["Travel/loading time"][i]
                    supplier = schedule_df["Supplier names"][i]
                    cost = schedule_df["Cost"][i]
                    distance = schedule_df["Distance travelled"][i]
                    parts_collected_dic = schedule_df["Parts collected"][i]
                    supplier_address = schedule_df["Supplier addresses"][i]
                    loading_percentage = schedule_df["Loading percentage"][i]
                    latest_arrival_time = schedule_df["Latest arrival time"][i]

                    # Append trip
                    van_IDs_list_late.append(van_ID)
                    van_sizes_list_late.append(van_size)
                    trip_numbers_list_late.append(trip_number)
                    arrival_times_list_late.append(arrival_time)
                    travel_times_list_late.append(travel_time)
                    suppliers_list_late.append(supplier)
                    costs_list_late.append(cost)
                    distances_list_late.append(distance)
                    parts_collected_list_late.append(parts_collected_dic)
                    supplier_addresses_list_late.append(supplier_address)
                    loading_percentages_list_late.append(loading_percentage)
                    latest_arrival_times_list_late.append(latest_arrival_time)

            index = max_index
        # update in version 3.0.011
        rows = schedule_df.index[index_list]
        # schedule_df.drop(rows, inplace=True)
        overnight_schedule_df = pd.DataFrame({"Van ID": van_IDs_list_late, "Supplier names": suppliers_list_late,
                                              "Arrival time": arrival_times_list_late,
                                              "Latest arrival time": latest_arrival_times_list_late,
                                              "Travel/loading time": travel_times_list_late,
                                              "Van size": van_sizes_list_late,
                                              "Parts collected": parts_collected_list_late,
                                              "Trip number": trip_numbers_list_late, "Cost": costs_list_late,
                                              "Distance travelled": distances_list_late,
                                              "Supplier addresses": supplier_addresses_list_late,
                                              "Loading percentage": loading_percentages_list_late})

        # Late items dataframe
        description = "隔夜交货"
        for i in range(len(overnight_schedule_df)):
            late_parts_list.append(overnight_schedule_df["Parts collected"][i])
            latest_times_late_list.append(overnight_schedule_df["Latest arrival time"][i])
            scheduled_times_late_list.append(overnight_schedule_df["Arrival time"][i])
            descriptions_list.append(description)
        late_items_df = pd.DataFrame({"Part IDs": late_parts_list, "Scheduled delivery time": scheduled_times_late_list,
                                      "Latest arrival time": latest_times_late_list, "Description": descriptions_list})

        return schedule_df, overnight_schedule_df, late_items_df, missing_suppliers

    #
    def algorithm_2(self, latest_arrival_time_df, van_info, schedule_date, schedule_end_date):
        '''

        '''
        # Choose hyperparameters
        max_run_number = 2 # Min 2

        send_back_to_factory = True
        missing_suppliers = []

        late_parts_list = []
        scheduled_times_late_list = []
        latest_times_late_list = []
        descriptions_list = []

        # Split car parts by supplier
        supplier_products_lists = self.split_parts_by_supplier(latest_arrival_time_df.copy())

        # Pack boxes into trays and sort trays and racks by arrival time / SNP
        supplier_racks_and_trays_lists = self.packing_algorithms.pack_trays_and_sort(supplier_products_lists.copy())

        # Organise trips
        van_IDs_list = []
        van_sizes_list = []
        trip_numbers_list = []
        number_suppliers_visited = []
        arrival_times_list = []
        travel_times_list = []
        suppliers_list = []
        costs_list = []
        distances_list = []
        parts_collected_list = []
        supplier_addresses_list = []
        loading_percentages_list = []
        list_stockpile_changes = []
        list_part_arrival_times = []
        latest_arrival_times_list = []

        while len(supplier_racks_and_trays_lists) > 0:

            continue_loop = True

            # Sort vans
            van_info = sorted(van_info, key=lambda x: (x[6], x[3]))
            logging.debug("van_info: {}".format(van_info))
            previous_arrival_time = van_info[0][3]

            # Set initial space in van
            spaces = "None"

            # First trip
            first_trip = True

            # Set initial loading rate
            loading_percentage = 0

            # Number of runs in this trip
            run_number = 0

            # Find earliest time for products to arrive
            earliest_date = routing_algorithms.find_earliest_date(supplier_racks_and_trays_lists.copy())
            logging.debug(f"earliest_date type: {earliest_date}({type(earliest_date)})...")

            # Find list of suppliers which have products next needed (by latest arrival time)
            supplier_list = routing_algorithms.find_supplier_list(supplier_racks_and_trays_lists.copy(), earliest_date)

            # Order suppliers by volume of items required for earliest arrival time
            supplier_list = routing_algorithms.order_suppliers_by_volume_of_items2(supplier_list.copy(),
                                                                                   supplier_racks_and_trays_lists.copy())

            # Limit number of suppliers that can be visited to 4
            supplier_list = supplier_list[:4]

            # Record factory crossings we wish to visit
            crossings = []
            send_back_to_factory = True

            while continue_loop is True:

                if first_trip:

                    # Choose first supplier
                    supplier = supplier_list[0]
                    van_info_, supplier_address, distance, travel_time, supplier_racks_and_trays_lists, cost, space_left, parts_collected_dic, trip_loading_percentage, van_ID, van_size, trip_number, arrival_time, late_parts_list, scheduled_times_late_list, latest_times_late_list, descriptions_list, space_left, latest_arrival_time = self.organise_trip(
                        supplier, self.factory_No, van_info.copy(), self.rest_times,
                        supplier_racks_and_trays_lists.copy(),
                        schedule_date, spaces=spaces)
                    supplier_list.pop(0)

                else:
                    if run_number > max_run_number:
                        # Ensure trip goes back to factory
                        trips_outputs = []
                    else:
                        # Find suppliers we can empty
                        trips_outputs = {}
                        time = earliest_date + datetime.timedelta(hours=2)

                        for supplier in supplier_list:
                            OUTPUT = self.organise_trip(supplier, self.factory_No, van_info.copy(), self.rest_times,
                                                        supplier_racks_and_trays_lists.copy(), schedule_date,
                                                        spaces=spaces.copy())
                            if supplier not in OUTPUT[4]:
                                trips_outputs[supplier] = OUTPUT

                    if len(trips_outputs) > 0:

                        # Choose supplier with most items from suppliers we can empty
                        volume_items = 0
                        index = list(trips_outputs.keys())[0]
                        for supplier in trips_outputs:
                            if trips_outputs[supplier][8] > volume_items:
                                volume_items = trips_outputs[supplier][8]
                                index = supplier
                        van_info_, supplier_address, distance, travel_time, supplier_racks_and_trays_lists, cost, space_left, parts_collected_dic, trip_loading_percentage, van_ID, van_size, trip_number, arrival_time, late_parts_list, scheduled_times_late_list, latest_times_late_list, descriptions_list, space_left, latest_arrival_time_ = \
                            trips_outputs[index]
                        supplier = index
                        supplier_list.remove(supplier)

                    else:

                        # Go minimum trip home
                        if len(supplier_list) < 1:
                            parts_collected_dic = {}
                        else:
                            if len(supplier_list) == 1:
                                supplier = supplier_list[0]
                            elif len(supplier_list) > 1:
                                supplier = self.order_suppliers_by_minimal_total_travel_time(supplier,
                                                                                             supplier_list.copy())
                            van_info_, supplier_address, distance, travel_time, supplier_racks_and_trays_lists, cost, space_left, parts_collected_dic, trip_loading_percentage, van_ID, van_size, trip_number, arrival_time, late_parts_list, scheduled_times_late_list, latest_times_late_list, descriptions_list, space_left, latest_arrival_time_ = self.organise_trip(
                                supplier, self.factory_No, van_info.copy(), self.rest_times,
                                supplier_racks_and_trays_lists.copy(), schedule_date, spaces=spaces)
                            supplier_list.remove(supplier)

                        if len(parts_collected_dic) == 0:
                            # Send van back to factory
                            supplier = suppliers_list[-1]
                            supplier_address, distance, travel_time = self.find_supplier_information_home(
                                supplier, self.factory_No, crossings)
                            arrival_time = arrival_times_list[-1] + travel_time
                            travel_time = (datetime.datetime.min + travel_time).time()
                            # 这里因为是回返回工厂，所以不需要再重复计算车辆每日固定成本，只需要计算运营成本 +_+
                            cost = distance / 1000 * van_info[0][5]
                            logging.info(f">>> car come back cost: {cost}")
                            parts_collected_dic = ""
                            if self.factory_No == 1:
                                supplier = "一工厂"
                            elif self.factory_No == 2:
                                supplier = "二工厂"
                            elif self.factory_No == 3:
                                supplier = "三工厂"
                            else:
                                supplier = "未知工厂"
                            supplier_address = "重庆市江北区两江大道233号"
                            supplier_coordinate = "106.762841,29.632332"

                            # Update run number
                            run_number += 1

                            # Update loading percentage
                            loading_percentage = " "

                            # Append trip
                            van_IDs_list.append(van_ID)
                            van_sizes_list.append(van_size)
                            trip_numbers_list.append(trip_number)
                            arrival_times_list.append(arrival_time)
                            travel_times_list.append(travel_time)
                            suppliers_list.append(supplier)
                            costs_list.append(cost)
                            distances_list.append(distance)
                            parts_collected_list.append(parts_collected_dic)
                            supplier_addresses_list.append(supplier_address)
                            loading_percentages_list.append(loading_percentage)
                            latest_arrival_times_list.append(latest_arrival_time)

                            # End trip for van
                            continue_loop = False
                            break

                    # Find arrival time, travel time, distance, and cost
                    supplier_address, distance, travel_time, flag = self.find_supplier_distances(supplier,
                                                                                                 suppliers_list[-1])
                    arrival_time = arrival_times_list[-1] + travel_time
                    travel_time = (datetime.datetime.min + travel_time).time()
                    # 判断该卡车是否已经在计算车辆每日固定成本，如果没有，则计算，如果已经计算过，则不需要再计算
                    if van_ID in self.car_is_cal_solid_cost_list:
                        cost = distance / 1000 * van_info[0][5]
                    else:
                        cost = van_info[0][4] + distance / 1000 * van_info[0][5]
                        self.car_is_cal_solid_cost_list.append(van_ID)

                    if not flag:
                        missing_suppliers.append(supplier)

                # Subsequent trips are different to first trip
                first_trip = False

                # Update van space
                spaces = space_left

                # Check if suppliers is empty
                if len(supplier_racks_and_trays_lists) == 0:
                    continue_loop = False

                # Update loading rate
                loading_percentage += trip_loading_percentage

                # Update run number
                run_number += 1

                # Add factory crossings to visit
                for part in parts_collected_dic:
                    index = self.car_part_df.index[self.car_part_df["ID"] == part].tolist()[0]
                    crossing = self.car_part_df["Unloading crossing"][index]
                    if crossing not in crossings:
                        crossings.append(crossing)

                # Append trip
                van_IDs_list.append(van_ID)
                van_sizes_list.append(van_size)
                trip_numbers_list.append(trip_number)
                arrival_times_list.append(arrival_time)
                travel_times_list.append(travel_time)
                suppliers_list.append(supplier)
                costs_list.append(cost)
                distances_list.append(distance)
                parts_collected_list.append(parts_collected_dic)
                supplier_addresses_list.append(supplier_address)
                loading_percentages_list.append(loading_percentage)
                latest_arrival_times_list.append(" ")

            # Change trip times for first trip
            if trip_number == 1:
                list_length = len(van_IDs_list)
                arrival_times_list[-1] = schedule_date
                for i in range(run_number - 1):
                    travel_time = datetime.datetime.combine(datetime.datetime.min,
                                                            travel_times_list[-i - 1]) - datetime.datetime.min
                    arrival_times_list[-i - 2] = arrival_times_list[-i - 1] - travel_time

            # Update van info
            trip_info = list(van_info[0])
            trip_info[2] += 1
            trip_info[3] = arrival_times_list[-1]
            if trip_info[3] < previous_arrival_time:
                trip_info[6] += 1
            van_info[0] = tuple(trip_info)

            # Remove van if this was its final trip
            van_infos = van_info.copy()
            if trip_number > 3:
                van_info.pop(0)

            # Append all items to late list if there are no more vans
            if len(van_info) > 0:
                pass
            else:
                if len(supplier_racks_and_trays_lists) > 0:
                    list_of_parts = supplier_racks_and_trays_lists.copy()
                    description = "车辆不足"
                    scheduled_time = " "
                    for supplier in list_of_parts:
                        for i in range(len(list_of_parts[supplier])):
                            late_parts_list.append(list_of_parts[supplier][i][0])
                            latest_times_late_list.append(list_of_parts[supplier][i][2])
                            scheduled_times_late_list.append(scheduled_time)
                            descriptions_list.append(description)
                    supplier_racks_and_trays_lists = {}
                    continue_loop = False
                    send_back_to_factory = False

        if send_back_to_factory and len(van_info) > 0:
            # Send van back to factory
            supplier_address, distance, travel_time = self.find_supplier_information(supplier, self.factory_No)
            arrival_time = arrival_times_list[-1] + travel_time
            travel_time = (datetime.datetime.min + travel_time).time()
            logging.debug(van_info)
            if van_ID in self.car_is_cal_solid_cost_list:
                cost = distance / 1000 * van_info[0][5]
            else:
                cost = van_info[0][4] + distance / 1000 * van_info[0][5]
                self.car_is_cal_solid_cost_list.append(van_ID)
            parts_collected_dic = ""
            if self.factory_No == 1:
                supplier = "一工厂"
            elif self.factory_No == 2:
                supplier = "二工厂"
            elif self.factory_No == 3:
                supplier = "三工厂"
            else:
                supplier = "未知工厂"
            supplier_address = "重庆市江北区两江大道233号"

            # Append trip
            van_IDs_list.append(van_ID)
            van_sizes_list.append(van_size)
            trip_numbers_list.append(trip_number)
            arrival_times_list.append(arrival_time)
            travel_times_list.append(travel_time)
            suppliers_list.append(supplier)
            costs_list.append(cost)
            distances_list.append(distance)
            parts_collected_list.append(parts_collected_dic)
            supplier_addresses_list.append(supplier_address)
            loading_percentages_list.append(loading_percentage)
            latest_arrival_times_list.append(latest_arrival_time)

        # Produce dataframe (main output)
        schedule_df = pd.DataFrame(
            {"Van ID": van_IDs_list, "Supplier names": suppliers_list, "Arrival time": arrival_times_list,
             "Latest arrival time": latest_arrival_times_list, "Travel/loading time": travel_times_list,
             "Van size": van_sizes_list, "Parts collected": parts_collected_list, "Trip number": trip_numbers_list,
             "Cost": costs_list, "Distance travelled": distances_list, "Supplier addresses": supplier_addresses_list,
             "Loading percentage": loading_percentages_list})

        # Produce overnight schedule
        van_IDs_list_late = []
        van_sizes_list_late = []
        trip_numbers_list_late = []
        arrival_times_list_late = []
        travel_times_list_late = []
        suppliers_list_late = []
        costs_list_late = []
        distances_list_late = []
        parts_collected_list_late = []
        supplier_addresses_list_late = []
        loading_percentages_list_late = []
        latest_arrival_times_list_late = []

        index_list = []
        van_ID_list = list(set(list(schedule_df["Van ID"])))
        for van_ID_ in van_ID_list:
            overnight_run = False
            index = schedule_df.index[schedule_df["Van ID"] == van_ID_].tolist()[0]
            for i in range(len(schedule_df)):
                if schedule_df["Van ID"][i] == van_ID_:
                    if schedule_df["Arrival time"][i] > schedule_end_date:
                        overnight_run = True
                        break
            if overnight_run:
                current_trip_number = schedule_df["Trip number"][i]
                for j in range(i):
                    if all([schedule_df["Van ID"][j] == van_ID_, schedule_df["Trip number"][j] == current_trip_number]):
                        i = j
                        break
                for j in range(i, len(schedule_df)):
                    if schedule_df["Van ID"][j] == van_ID_:
                        index_list.append(j)
                        # Append trip
                        van_IDs_list_late.append(schedule_df["Van ID"][j])
                        van_sizes_list_late.append(schedule_df["Van size"][j])
                        trip_numbers_list_late.append(schedule_df["Trip number"][j])
                        arrival_times_list_late.append(schedule_df["Arrival time"][j])
                        travel_times_list_late.append(schedule_df["Travel/loading time"][j])
                        suppliers_list_late.append(schedule_df["Supplier names"][j])
                        costs_list_late.append(schedule_df["Cost"][j])
                        distances_list_late.append(schedule_df["Distance travelled"][j])
                        parts_collected_list_late.append(schedule_df["Parts collected"][j])
                        supplier_addresses_list_late.append(schedule_df["Supplier addresses"][j])
                        loading_percentages_list_late.append(schedule_df["Loading percentage"][j])
                        latest_arrival_times_list_late.append(schedule_df["Latest arrival time"][j])
        rows = schedule_df.index[index_list]
        schedule_df.drop(rows, inplace=True)

        overnight_schedule_df = pd.DataFrame({"Van ID": van_IDs_list_late, "Supplier names": suppliers_list_late,
                                              "Arrival time": arrival_times_list_late,
                                              "Latest arrival time": latest_arrival_times_list_late,
                                              "Travel/loading time": travel_times_list_late,
                                              "Van size": van_sizes_list_late,
                                              "Parts collected": parts_collected_list_late,
                                              "Trip number": trip_numbers_list_late, "Cost": costs_list_late,
                                              "Distance travelled": distances_list_late,
                                              "Supplier addresses": supplier_addresses_list_late,
                                              "Loading percentage": loading_percentages_list_late})

        # Late items dataframe
        description = "隔夜交货"
        for i in range(len(overnight_schedule_df)):
            late_parts_list.append(overnight_schedule_df["Parts collected"][i])
            latest_times_late_list.append(overnight_schedule_df["Latest arrival time"][i])
            scheduled_times_late_list.append(overnight_schedule_df["Arrival time"][i])
            descriptions_list.append(description)
        late_items_df = pd.DataFrame({"Part IDs": late_parts_list, "Scheduled delivery time": scheduled_times_late_list,
                                      "Latest arrival time": latest_times_late_list, "Description": descriptions_list})

        return schedule_df, overnight_schedule_df, late_items_df, missing_suppliers

    #
    def algorithm_3(self, latest_arrival_time_df, van_info, schedule_date, schedule_end_date):
        '''

        '''
        # Choose hyperparameters
        max_run_number = 1 # min 1

        send_back_to_factory = True
        missing_suppliers = []
        late_parts_list = []
        scheduled_times_late_list = []
        latest_times_late_list = []
        descriptions_list = []

        # Split car parts by supplier
        supplier_products_lists = self.split_parts_by_supplier(latest_arrival_time_df.copy())

        # Pack boxes into trays and sort trays and racks by arrival time / SNP
        supplier_racks_and_trays_lists = self.packing_algorithms.pack_trays_and_sort(supplier_products_lists)

        # Organise trips
        van_IDs_list = []
        van_sizes_list = []
        trip_numbers_list = []
        number_suppliers_visited = []
        arrival_times_list = []
        travel_times_list = []
        suppliers_list = []
        costs_list = []
        distances_list = []
        parts_collected_list = []
        supplier_addresses_list = []
        loading_percentages_list = []
        list_stockpile_changes = []
        list_part_arrival_times = []
        latest_arrival_times_list = []
        while len(supplier_racks_and_trays_lists) > 0:

            continue_loop = True

            # Sort vans
            van_info = sorted(van_info, key=lambda x: (x[6], x[3]))
            previous_arrival_time = van_info[0][3]

            # Set initial space in van
            spaces = "None"

            # First trip
            first_trip = True

            # Set initial loading rate
            loading_percentage = 0

            # Number of runs in this trip
            run_number = 0

            # Find earliest time for products to arrive
            earliest_date = routing_algorithms.find_earliest_date(supplier_racks_and_trays_lists)

            # Find list of suppliers which have products next needed (by latest arrival time)
            supplier_list = routing_algorithms.find_supplier_list(supplier_racks_and_trays_lists, earliest_date)

            # Order suppliers by volume of items required for earliest arrival time
            supplier_list = self.order_suppliers_by_distance(supplier_list, supplier_racks_and_trays_lists)

            # Limit number of suppliers that can be visited to 4
            supplier_list = supplier_list[:4]

            # Record factory crossings we wish to visit
            crossings = []
            send_back_to_factory = True

            while continue_loop is True:

                if first_trip:

                    # Choose first supplier
                    supplier = supplier_list[0]
                    van_info_, supplier_address, distance, travel_time, supplier_racks_and_trays_lists, cost, space_left, parts_collected_dic, trip_loading_percentage, van_ID, van_size, trip_number, arrival_time, late_parts_list, scheduled_times_late_list, latest_times_late_list, descriptions_list, space_left, latest_arrival_time = self.organise_trip(
                        supplier, self.factory_No, van_info.copy(), self.rest_times, supplier_racks_and_trays_lists,
                        schedule_date, spaces=spaces)
                    supplier_list.pop(0)

                else:
                    if run_number > max_run_number:
                        parts_collected_dic = {}
                    elif len(supplier_list)<1:
                        parts_collected_dic = {}
                    else:
                        supplier_list.append(supplier)
                        supplier = self.order_suppliers_by_minimal_total_travel_time(supplier,
                                                                                     supplier_list.copy())
                        van_info_, supplier_address, distance, travel_time, supplier_racks_and_trays_lists, cost, space_left, parts_collected_dic, trip_loading_percentage, van_ID, van_size, trip_number, arrival_time, late_parts_list, scheduled_times_late_list, latest_times_late_list, descriptions_list, space_left, latest_arrival_time_ = self.organise_trip(
                            supplier, self.factory_No, van_info.copy(), self.rest_times, supplier_racks_and_trays_lists,
                            schedule_date, spaces=spaces)
                        supplier_list.pop()
                        supplier_list.remove(supplier)

                    if len(parts_collected_dic) == 0:
                        # Send van back to factory
                        supplier = suppliers_list[-1]
                        supplier_address, distance, travel_time = self.find_supplier_information_home(
                            supplier, self.factory_No, crossings)
                        arrival_time = arrival_times_list[-1] + travel_time
                        travel_time = (datetime.datetime.min + travel_time).time()
                        # 这里因为是回返回工厂，所以不需要再重复计算车辆每日固定成本，只需要计算运营成本 +_+
                        cost = distance / 1000 * van_info[0][5]
                        logging.info(f">>> car come back cost: {cost}")
                        parts_collected_dic = ""
                        if self.factory_No == 1:
                            supplier = "一工厂"
                        elif self.factory_No == 2:
                            supplier = "二工厂"
                        elif self.factory_No == 3:
                            supplier = "三工厂"
                        else:
                            supplier = "未知工厂"

                        # Update run number
                        run_number += 1

                        # Update loading percentage
                        loading_percentage = " "

                        # Append trip
                        van_IDs_list.append(van_ID)
                        van_sizes_list.append(van_size)
                        trip_numbers_list.append(trip_number)
                        arrival_times_list.append(arrival_time)
                        travel_times_list.append(travel_time)
                        suppliers_list.append(supplier)
                        costs_list.append(cost)
                        distances_list.append(distance)
                        parts_collected_list.append(parts_collected_dic)
                        supplier_addresses_list.append(supplier_address)
                        loading_percentages_list.append(loading_percentage)
                        latest_arrival_times_list.append(latest_arrival_time)

                        # End trip for van
                        continue_loop = False
                        break

                    # Find arrival time, travel time, distance, and cost
                    supplier_address, distance, travel_time, flag = self.find_supplier_distances(supplier,
                                                                                                 suppliers_list[-1])
                    arrival_time = arrival_times_list[-1] + travel_time
                    travel_time = (datetime.datetime.min + travel_time).time()
                    # 判断该卡车是否已经在计算车辆每日固定成本，如果没有，则计算，如果已经计算过，则不需要再计算
                    if van_ID in self.car_is_cal_solid_cost_list:
                        cost = distance / 1000 * van_info[0][5]
                    else:
                        cost = van_info[0][4] + distance / 1000 * van_info[0][5]
                        self.car_is_cal_solid_cost_list.append(van_ID)

                    if not flag:
                        missing_suppliers.append(supplier)

                # Subsequent trips are different to first trip
                first_trip = False

                # Update van space
                spaces = space_left

                # Check if suppliers is empty
                if len(supplier_racks_and_trays_lists) == 0:
                    continue_loop = False

                # Update loading rate
                loading_percentage += trip_loading_percentage

                # Update run number
                run_number += 1

                # Add factory crossings to visit
                for part in parts_collected_dic:
                    index = self.car_part_df.index[self.car_part_df["ID"] == part].tolist()[0]
                    crossing = self.car_part_df["Unloading crossing"][index]
                    if crossing not in crossings:
                        crossings.append(crossing)

                # Append trip
                van_IDs_list.append(van_ID)
                van_sizes_list.append(van_size)
                trip_numbers_list.append(trip_number)
                arrival_times_list.append(arrival_time)
                travel_times_list.append(travel_time)
                suppliers_list.append(supplier)
                costs_list.append(cost)
                distances_list.append(distance)
                parts_collected_list.append(parts_collected_dic)
                supplier_addresses_list.append(supplier_address)
                loading_percentages_list.append(loading_percentage)
                latest_arrival_times_list.append(" ")

            # Change trip times for first trip
            if trip_number == 1:
                list_length = len(van_IDs_list)
                arrival_times_list[-1] = schedule_date
                for i in range(run_number - 1):
                    travel_time = datetime.datetime.combine(datetime.datetime.min,
                                                            travel_times_list[-i - 1]) - datetime.datetime.min
                    arrival_times_list[-i - 2] = arrival_times_list[-i - 1] - travel_time
            # Update van info
            trip_info = list(van_info[0])
            trip_info[2] += 1
            trip_info[3] = arrival_times_list[-1]
            if trip_info[3] < previous_arrival_time:
                trip_info[6] += 1
            van_info[0] = tuple(trip_info)

            # Remove van if this was its final trip
            van_infos = van_info.copy()
            if trip_number > 3:
                van_info.pop(0)

            # Append all items to late list if there are no more vans
            if len(van_info) > 0:
                pass
            else:
                if len(supplier_racks_and_trays_lists) > 0:
                    list_of_parts = supplier_racks_and_trays_lists.copy()
                    description = "车辆不足"
                    scheduled_time = " "
                    for supplier in list_of_parts:
                        for i in range(len(list_of_parts[supplier])):
                            late_parts_list.append(list_of_parts[supplier][i][0])
                            latest_times_late_list.append(list_of_parts[supplier][i][2])
                            scheduled_times_late_list.append(scheduled_time)
                            descriptions_list.append(description)
                    supplier_racks_and_trays_lists = {}
                    continue_loop = False
                    send_back_to_factory = False

        if send_back_to_factory and len(van_info) > 0:
            # Send van back to factory
            supplier_address, distance, travel_time = self.find_supplier_information(supplier, self.factory_No)
            arrival_time = arrival_times_list[-1] + travel_time
            travel_time = (datetime.datetime.min + travel_time).time()
            # 这里因为是回返回工厂，所以不需要再重复计算车辆每日固定成本，只需要计算运营成本 +_+
            cost = distance / 1000 * van_info[0][5]
            logging.info(f">>> car come back cost: {cost}")
            parts_collected_dic = ""
            if self.factory_No == 1:
                supplier = "一工厂"
            elif self.factory_No == 2:
                supplier = "二工厂"
            elif self.factory_No == 3:
                supplier = "三工厂"
            else:
                supplier = "未知工厂"
            supplier_address = "重庆市江北区两江大道233号"

            # Append trip
            van_IDs_list.append(van_ID)
            van_sizes_list.append(van_size)
            trip_numbers_list.append(trip_number)
            arrival_times_list.append(arrival_time)
            travel_times_list.append(travel_time)
            suppliers_list.append(supplier)
            costs_list.append(cost)
            distances_list.append(distance)
            parts_collected_list.append(parts_collected_dic)
            supplier_addresses_list.append(supplier_address)
            loading_percentages_list.append(loading_percentage)
            latest_arrival_times_list.append(latest_arrival_time)

        # Produce dataframe (main output)
        schedule_df = pd.DataFrame(
            {"Van ID": van_IDs_list, "Supplier names": suppliers_list, "Arrival time": arrival_times_list,
             "Latest arrival time": latest_arrival_times_list, "Travel/loading time": travel_times_list,
             "Van size": van_sizes_list, "Parts collected": parts_collected_list, "Trip number": trip_numbers_list,
             "Cost": costs_list, "Distance travelled": distances_list, "Supplier addresses": supplier_addresses_list,
             "Loading percentage": loading_percentages_list})

        # Produce overdate schedule
        van_IDs_list_late = []
        van_sizes_list_late = []
        trip_numbers_list_late = []
        arrival_times_list_late = []
        travel_times_list_late = []
        suppliers_list_late = []
        costs_list_late = []
        distances_list_late = []
        parts_collected_list_late = []
        supplier_addresses_list_late = []
        loading_percentages_list_late = []
        latest_arrival_times_list_late = []

        index_list = []
        van_ID_list = list(set(list(schedule_df["Van ID"])))
        for van_ID_ in van_ID_list:
            overnight_run = False
            index = schedule_df.index[schedule_df["Van ID"] == van_ID_].tolist()[0]
            for i in range(len(schedule_df)):
                if schedule_df["Van ID"][i] == van_ID_:
                    if schedule_df["Arrival time"][i] > schedule_end_date:
                        overnight_run = True
                        break
            if overnight_run:
                current_trip_number = schedule_df["Trip number"][i]
                for j in range(i):
                    if all([schedule_df["Van ID"][j] == van_ID_, schedule_df["Trip number"][j] == current_trip_number]):
                        i = j
                        break
                for j in range(i, len(schedule_df)):
                    if schedule_df["Van ID"][j] == van_ID_:
                        index_list.append(j)
                        # Append trip
                        van_IDs_list_late.append(schedule_df["Van ID"][j])
                        van_sizes_list_late.append(schedule_df["Van size"][j])
                        trip_numbers_list_late.append(schedule_df["Trip number"][j])
                        arrival_times_list_late.append(schedule_df["Arrival time"][j])
                        travel_times_list_late.append(schedule_df["Travel/loading time"][j])
                        suppliers_list_late.append(schedule_df["Supplier names"][j])
                        costs_list_late.append(schedule_df["Cost"][j])
                        distances_list_late.append(schedule_df["Distance travelled"][j])
                        parts_collected_list_late.append(schedule_df["Parts collected"][j])
                        supplier_addresses_list_late.append(schedule_df["Supplier addresses"][j])
                        loading_percentages_list_late.append(schedule_df["Loading percentage"][j])
                        latest_arrival_times_list_late.append(schedule_df["Latest arrival time"][j])
        rows = schedule_df.index[index_list]
        schedule_df.drop(rows, inplace=True)

        overnight_schedule_df = pd.DataFrame({"Van ID": van_IDs_list_late, "Supplier names": suppliers_list_late,
                                              "Arrival time": arrival_times_list_late,
                                              "Latest arrival time": latest_arrival_times_list_late,
                                              "Travel/loading time": travel_times_list_late,
                                              "Van size": van_sizes_list_late,
                                              "Parts collected": parts_collected_list_late,
                                              "Trip number": trip_numbers_list_late, "Cost": costs_list_late,
                                              "Distance travelled": distances_list_late,
                                              "Supplier addresses": supplier_addresses_list_late,
                                              "Loading percentage": loading_percentages_list_late})

        # Late items dataframe
        description = "隔夜交货"
        for i in range(len(overnight_schedule_df)):
            late_parts_list.append(overnight_schedule_df["Parts collected"][i])
            latest_times_late_list.append(overnight_schedule_df["Latest arrival time"][i])
            scheduled_times_late_list.append(overnight_schedule_df["Arrival time"][i])
            descriptions_list.append(description)
        late_items_df = pd.DataFrame({"Part IDs": late_parts_list, "Scheduled delivery time": scheduled_times_late_list,
                                      "Latest arrival time": latest_times_late_list, "Description": descriptions_list})

        return schedule_df, overnight_schedule_df, late_items_df, missing_suppliers


    def algorithm_4(self, latest_arrival_time_df, van_info, schedule_date, schedule_end_date):
        '''

        '''
        # Choose hyperparameters
        max_run_number = 1000000  # Min 2

        # 最低装载率
        min_loading_percentage = 0.55

        send_back_to_factory = True
        missing_suppliers = []

        late_parts_list = []
        scheduled_times_late_list = []
        latest_times_late_list = []
        descriptions_list = []

        # Split car parts by supplier
        supplier_products_lists = self.split_parts_by_supplier(latest_arrival_time_df.copy())

        # Pack boxes into trays and sort trays and racks by arrival time / SNP
        supplier_racks_and_trays_lists = self.packing_algorithms.pack_trays_and_sort(supplier_products_lists.copy())

        # Organise trips
        van_IDs_list = []
        van_sizes_list = []
        trip_numbers_list = []
        number_suppliers_visited = []
        arrival_times_list = []
        travel_times_list = []
        suppliers_list = []
        costs_list = []
        distances_list = []
        parts_collected_list = []
        supplier_addresses_list = []
        loading_percentages_list = []
        list_stockpile_changes = []
        list_part_arrival_times = []
        latest_arrival_times_list = []

        while len(supplier_racks_and_trays_lists) > 0:

            continue_loop = True

            # Sort vans
            van_info = sorted(van_info, key=lambda x: (x[6], x[3]))
            logging.debug("van_info: {}".format(van_info))
            previous_arrival_time = van_info[0][3]

            # Set initial space in van
            spaces = "None"

            # First trip
            first_trip = True

            # Set initial loading rate
            loading_percentage = 0

            # Number of runs in this trip
            run_number = 0

            # Find earliest time for products to arrive
            earliest_date = routing_algorithms.find_earliest_date(supplier_racks_and_trays_lists.copy())
            logging.debug(f"earliest_date type: {earliest_date}({type(earliest_date)})...")

            # Find list of suppliers which have products next needed (by latest arrival time)
            hours = 24
            supplier_list = routing_algorithms.find_supplier_list(supplier_racks_and_trays_lists.copy(), earliest_date, hours=hours)

            # Order suppliers by volume of items required for earliest arrival time
            supplier_list = routing_algorithms.order_suppliers_by_volume_of_items(supplier_list.copy(),
                                                                                   supplier_racks_and_trays_lists.copy())

            # Limit number of suppliers that can be visited to 4
            # supplier_list = supplier_list[:4]

            # Record factory crossings we wish to visit
            crossings = []
            send_back_to_factory = True

            while continue_loop is True:

                if first_trip:

                    # Choose first supplier
                    supplier = supplier_list[0]
                    van_info_, supplier_address, distance, travel_time, supplier_racks_and_trays_lists, cost, space_left, parts_collected_dic, trip_loading_percentage, van_ID, van_size, trip_number, arrival_time, late_parts_list, scheduled_times_late_list, latest_times_late_list, descriptions_list, space_left, latest_arrival_time = self.organise_trip(
                        supplier, self.factory_No, van_info.copy(), self.rest_times,
                        supplier_racks_and_trays_lists.copy(),
                        schedule_date, spaces=spaces, hours=hours)
                    supplier_list.pop(0)

                else:
                    if run_number > max_run_number:
                        # Ensure trip goes back to factory
                        trips_outputs = []
                    else:
                        # Find suppliers we can empty
                        trips_outputs = {}
                        time = earliest_date + datetime.timedelta(hours=hours)

                        for supplier in supplier_list:
                            OUTPUT = self.organise_trip(supplier, self.factory_No, van_info.copy(), self.rest_times,
                                                        supplier_racks_and_trays_lists.copy(), schedule_date,
                                                        spaces=spaces.copy(), hours=hours)
                            if supplier not in OUTPUT[4]:
                                trips_outputs[supplier] = OUTPUT

                    if len(trips_outputs) > 0:

                        # Choose supplier with most items from suppliers we can empty
                        volume_items = 0
                        index = list(trips_outputs.keys())[0]
                        for supplier in trips_outputs:
                            if trips_outputs[supplier][8] > volume_items:
                                volume_items = trips_outputs[supplier][8]
                                index = supplier
                        van_info_, supplier_address, distance, travel_time, supplier_racks_and_trays_lists, cost, space_left, parts_collected_dic, trip_loading_percentage, van_ID, van_size, trip_number, arrival_time, late_parts_list, scheduled_times_late_list, latest_times_late_list, descriptions_list, space_left, latest_arrival_time_ = \
                            trips_outputs[index]
                        supplier = index
                        supplier_list.remove(supplier)

                    else:
                        trip_loading_percentage = 0
                        parts_collected_dic = {}
                        current_supplier = supplier
                        while len(supplier_list) > 0 and loading_percentage + trip_loading_percentage < min_loading_percentage:
                            # Go minimum trip home
                            if len(supplier_list) == 1:
                                supplier = supplier_list[0]
                            elif len(supplier_list) > 1:
                                supplier = self.order_suppliers_by_minimal_total_travel_time(current_supplier,
                                                                                             supplier_list.copy())
                            van_info_, supplier_address, distance, travel_time, supplier_racks_and_trays_lists, cost, space_left, parts_collected_dic, trip_loading_percentage, van_ID, van_size, trip_number, arrival_time, late_parts_list, scheduled_times_late_list, latest_times_late_list, descriptions_list, space_left, latest_arrival_time_ = self.organise_trip(
                                supplier, self.factory_No, van_info.copy(), self.rest_times,
                                supplier_racks_and_trays_lists.copy(), schedule_date, spaces=spaces, hours=hours)
                            supplier_list.remove(supplier)

                            # Update van space
                            spaces = space_left

                            if len(parts_collected_dic) >= 1:
                                break

                        if len(parts_collected_dic) == 0:
                            # Send van back to factory
                            supplier = suppliers_list[-1]
                            supplier_address, distance, travel_time = self.find_supplier_information_home(
                                supplier, self.factory_No, crossings)
                            arrival_time = arrival_times_list[-1] + travel_time
                            travel_time = (datetime.datetime.min + travel_time).time()
                            # 这里因为是回返回工厂，所以不需要再重复计算车辆每日固定成本，只需要计算运营成本 +_+
                            cost = distance / 1000 * van_info[0][5]
                            logging.info(f">>> car come back cost: {cost}")
                            parts_collected_dic = ""
                            if self.factory_No == 1:
                                supplier = "一工厂"
                            elif self.factory_No == 2:
                                supplier = "二工厂"
                            elif self.factory_No == 3:
                                supplier = "三工厂"
                            else:
                                supplier = "未知工厂"
                            supplier_address = "重庆市江北区两江大道233号"
                            supplier_coordinate = "106.762841,29.632332"

                            # Update run number
                            run_number += 1

                            # Update loading percentage
                            loading_percentage = " "

                            # Append trip
                            van_IDs_list.append(van_ID)
                            van_sizes_list.append(van_size)
                            trip_numbers_list.append(trip_number)
                            arrival_times_list.append(arrival_time)
                            travel_times_list.append(travel_time)
                            suppliers_list.append(supplier)
                            costs_list.append(cost)
                            distances_list.append(distance)
                            parts_collected_list.append(parts_collected_dic)
                            supplier_addresses_list.append(supplier_address)
                            loading_percentages_list.append(loading_percentage)
                            latest_arrival_times_list.append(latest_arrival_time)

                            # End trip for van
                            continue_loop = False
                            break

                    # Find arrival time, travel time, distance, and cost
                    supplier_address, distance, travel_time, flag = self.find_supplier_distances(supplier,
                                                                                                 suppliers_list[-1])
                    arrival_time = arrival_times_list[-1] + travel_time
                    travel_time = (datetime.datetime.min + travel_time).time()
                    # 判断该卡车是否已经在计算车辆每日固定成本，如果没有，则计算，如果已经计算过，则不需要再计算
                    if van_ID in self.car_is_cal_solid_cost_list:
                        cost = distance / 1000 * van_info[0][5]
                    else:
                        cost = van_info[0][4] + distance / 1000 * van_info[0][5]
                        self.car_is_cal_solid_cost_list.append(van_ID)

                    if not flag:
                        missing_suppliers.append(supplier)

                # Subsequent trips are different to first trip
                first_trip = False

                # Update van space
                spaces = space_left

                # Check if suppliers is empty
                if len(supplier_racks_and_trays_lists) == 0:
                    continue_loop = False

                # Update loading rate
                loading_percentage += trip_loading_percentage

                # Update run number
                run_number += 1

                # Add factory crossings to visit
                for part in parts_collected_dic:
                    index = self.car_part_df.index[self.car_part_df["ID"] == part].tolist()[0]
                    crossing = self.car_part_df["Unloading crossing"][index]
                    if crossing not in crossings:
                        crossings.append(crossing)

                # Append trip
                van_IDs_list.append(van_ID)
                van_sizes_list.append(van_size)
                trip_numbers_list.append(trip_number)
                arrival_times_list.append(arrival_time)
                travel_times_list.append(travel_time)
                suppliers_list.append(supplier)
                costs_list.append(cost)
                distances_list.append(distance)
                parts_collected_list.append(parts_collected_dic)
                supplier_addresses_list.append(supplier_address)
                loading_percentages_list.append(loading_percentage)
                latest_arrival_times_list.append(" ")

                # 装载率大于等于55%时，就不去下一家供货商了，直接返厂
                if loading_percentage >= min_loading_percentage:
                    # Send van back to factory
                    supplier = suppliers_list[-1]
                    supplier_address, distance, travel_time = self.find_supplier_information_home(
                        supplier, self.factory_No, crossings)
                    arrival_time = arrival_times_list[-1] + travel_time
                    travel_time = (datetime.datetime.min + travel_time).time()
                    # 这里因为是回返回工厂，所以不需要再重复计算车辆每日固定成本，只需要计算运营成本 +_+
                    cost = distance / 1000 * van_info[0][5]
                    logging.info(f">>> car come back cost: {cost}")
                    parts_collected_dic = ""
                    if self.factory_No == 1:
                        supplier = "一工厂"
                    elif self.factory_No == 2:
                        supplier = "二工厂"
                    elif self.factory_No == 3:
                        supplier = "三工厂"
                    else:
                        supplier = "未知工厂"
                    supplier_address = "重庆市江北区两江大道233号"
                    supplier_coordinate = "106.762841,29.632332"

                    # Update run number
                    run_number += 1

                    # Update loading percentage
                    loading_percentage = " "

                    # Append trip
                    van_IDs_list.append(van_ID)
                    van_sizes_list.append(van_size)
                    trip_numbers_list.append(trip_number)
                    arrival_times_list.append(arrival_time)
                    travel_times_list.append(travel_time)
                    suppliers_list.append(supplier)
                    costs_list.append(cost)
                    distances_list.append(distance)
                    parts_collected_list.append(parts_collected_dic)
                    supplier_addresses_list.append(supplier_address)
                    loading_percentages_list.append(loading_percentage)
                    latest_arrival_times_list.append(latest_arrival_time)

                    # End trip for van
                    continue_loop = False
                    break

            # Change trip times for first trip
            if trip_number == 1:
                list_length = len(van_IDs_list)
                arrival_times_list[-1] = schedule_date
                for i in range(run_number - 1):
                    travel_time = datetime.datetime.combine(datetime.datetime.min,
                                                            travel_times_list[-i - 1]) - datetime.datetime.min
                    arrival_times_list[-i - 2] = arrival_times_list[-i - 1] - travel_time

            # Update van info
            trip_info = list(van_info[0])
            trip_info[2] += 1
            trip_info[3] = arrival_times_list[-1]
            if trip_info[3] < previous_arrival_time:
                trip_info[6] += 1
            van_info[0] = tuple(trip_info)

            # Remove van if this was its final trip
            van_infos = van_info.copy()
            if trip_number > 3:
                van_info.pop(0)

            # Append all items to late list if there are no more vans
            if len(van_info) > 0:
                pass
            else:
                if len(supplier_racks_and_trays_lists) > 0:
                    list_of_parts = supplier_racks_and_trays_lists.copy()
                    description = "车辆不足"
                    scheduled_time = " "
                    for supplier in list_of_parts:
                        for i in range(len(list_of_parts[supplier])):
                            late_parts_list.append(list_of_parts[supplier][i][0])
                            latest_times_late_list.append(list_of_parts[supplier][i][2])
                            scheduled_times_late_list.append(scheduled_time)
                            descriptions_list.append(description)
                    supplier_racks_and_trays_lists = {}
                    continue_loop = False
                    send_back_to_factory = False

        if send_back_to_factory and len(van_info) > 0:
            # Send van back to factory
            supplier_address, distance, travel_time = self.find_supplier_information(supplier, self.factory_No)
            arrival_time = arrival_times_list[-1] + travel_time
            travel_time = (datetime.datetime.min + travel_time).time()
            logging.debug(van_info)
            if van_ID in self.car_is_cal_solid_cost_list:
                cost = distance / 1000 * van_info[0][5]
            else:
                cost = van_info[0][4] + distance / 1000 * van_info[0][5]
                self.car_is_cal_solid_cost_list.append(van_ID)
            parts_collected_dic = ""
            if self.factory_No == 1:
                supplier = "一工厂"
            elif self.factory_No == 2:
                supplier = "二工厂"
            elif self.factory_No == 3:
                supplier = "三工厂"
            else:
                supplier = "未知工厂"
            supplier_address = "重庆市江北区两江大道233号"

            # Append trip
            van_IDs_list.append(van_ID)
            van_sizes_list.append(van_size)
            trip_numbers_list.append(trip_number)
            arrival_times_list.append(arrival_time)
            travel_times_list.append(travel_time)
            suppliers_list.append(supplier)
            costs_list.append(cost)
            distances_list.append(distance)
            parts_collected_list.append(parts_collected_dic)
            supplier_addresses_list.append(supplier_address)
            loading_percentages_list.append(loading_percentage)
            latest_arrival_times_list.append(latest_arrival_time)

        # Produce dataframe (main output)
        schedule_df = pd.DataFrame(
            {"Van ID": van_IDs_list, "Supplier names": suppliers_list, "Arrival time": arrival_times_list,
             "Latest arrival time": latest_arrival_times_list, "Travel/loading time": travel_times_list,
             "Van size": van_sizes_list, "Parts collected": parts_collected_list, "Trip number": trip_numbers_list,
             "Cost": costs_list, "Distance travelled": distances_list, "Supplier addresses": supplier_addresses_list,
             "Loading percentage": loading_percentages_list})

        # Produce overnight schedule
        van_IDs_list_late = []
        van_sizes_list_late = []
        trip_numbers_list_late = []
        arrival_times_list_late = []
        travel_times_list_late = []
        suppliers_list_late = []
        costs_list_late = []
        distances_list_late = []
        parts_collected_list_late = []
        supplier_addresses_list_late = []
        loading_percentages_list_late = []
        latest_arrival_times_list_late = []

        index_list = []
        van_ID_list = list(set(list(schedule_df["Van ID"])))
        for van_ID_ in van_ID_list:
            overnight_run = False
            index = schedule_df.index[schedule_df["Van ID"] == van_ID_].tolist()[0]
            for i in range(len(schedule_df)):
                if schedule_df["Van ID"][i] == van_ID_:
                    if schedule_df["Arrival time"][i] > schedule_end_date:
                        overnight_run = True
                        break
            if overnight_run:
                current_trip_number = schedule_df["Trip number"][i]
                for j in range(i):
                    if all([schedule_df["Van ID"][j] == van_ID_, schedule_df["Trip number"][j] == current_trip_number]):
                        i = j
                        break
                for j in range(i, len(schedule_df)):
                    if schedule_df["Van ID"][j] == van_ID_:
                        index_list.append(j)
                        # Append trip
                        van_IDs_list_late.append(schedule_df["Van ID"][j])
                        van_sizes_list_late.append(schedule_df["Van size"][j])
                        trip_numbers_list_late.append(schedule_df["Trip number"][j])
                        arrival_times_list_late.append(schedule_df["Arrival time"][j])
                        travel_times_list_late.append(schedule_df["Travel/loading time"][j])
                        suppliers_list_late.append(schedule_df["Supplier names"][j])
                        costs_list_late.append(schedule_df["Cost"][j])
                        distances_list_late.append(schedule_df["Distance travelled"][j])
                        parts_collected_list_late.append(schedule_df["Parts collected"][j])
                        supplier_addresses_list_late.append(schedule_df["Supplier addresses"][j])
                        loading_percentages_list_late.append(schedule_df["Loading percentage"][j])
                        latest_arrival_times_list_late.append(schedule_df["Latest arrival time"][j])
        rows = schedule_df.index[index_list]
        schedule_df.drop(rows, inplace=True)

        overnight_schedule_df = pd.DataFrame({"Van ID": van_IDs_list_late, "Supplier names": suppliers_list_late,
                                              "Arrival time": arrival_times_list_late,
                                              "Latest arrival time": latest_arrival_times_list_late,
                                              "Travel/loading time": travel_times_list_late,
                                              "Van size": van_sizes_list_late,
                                              "Parts collected": parts_collected_list_late,
                                              "Trip number": trip_numbers_list_late, "Cost": costs_list_late,
                                              "Distance travelled": distances_list_late,
                                              "Supplier addresses": supplier_addresses_list_late,
                                              "Loading percentage": loading_percentages_list_late})

        # Late items dataframe
        description = "隔夜交货"
        for i in range(len(overnight_schedule_df)):
            late_parts_list.append(overnight_schedule_df["Parts collected"][i])
            latest_times_late_list.append(overnight_schedule_df["Latest arrival time"][i])
            scheduled_times_late_list.append(overnight_schedule_df["Arrival time"][i])
            descriptions_list.append(description)
        late_items_df = pd.DataFrame({"Part IDs": late_parts_list, "Scheduled delivery time": scheduled_times_late_list,
                                      "Latest arrival time": latest_times_late_list, "Description": descriptions_list})

        return schedule_df, overnight_schedule_df, late_items_df, missing_suppliers